Chia táo

Bạn có \(N\) quả táo với trọng lượng đã biết. Nhiệm vụ của bạn là chia \(N\) quả táo này thành hai nhóm, gọi là Nhóm A và Nhóm B, sao cho chênh lệch tuyệt đối về tổng trọng lượng giữa Nhóm A và Nhóm B là nhỏ nhất.

• Mỗi quả táo phải thuộc duy nhất một nhóm (A hoặc B).
• Nếu \(S_A\) là tổng trọng lượng của Nhóm A và \(S_B\) là tổng trọng lượng của Nhóm B, bạn cần tìm \(\min(|S_A - S_B|)\).

Input

• Dòng đầu tiên chứa một số nguyên \(N\) (\(1 \le N \le 20\)) --- số lượng táo.
• Dòng tiếp theo chứa \(N\) số nguyên \(p_1, p_2, \ldots, p_n\) (\(1 \le p_i \le 10^9\)) --- trọng lượng của mỗi quả táo.

Output

In ra một số nguyên duy nhất là chênh lệch trọng lượng tối thiểu giữa hai nhóm.

Example

5
3 2 7 4 1

1