Có \(n\) quả táo với trọng lượng đã biết. Nhiệm vụ của bạn là chia những quả táo thành hai nhóm sao cho chênh lệch trọng lượng giữa hai nhóm là tối thiểu.

Input

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

Output

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

Constraints

• \(1 \le n \le 20\)
• \(1 \le p_i \le 10^9\)

Example

Sample input

5
3 2 7 4 1

Sample output

1

Note

Nhóm \(1\) có trọng lượng \(2\), \(3\) và \(4\) (tổng là \(9\)), và nhóm \(2\) có trọng lượng \(1\) và \(7\) (tổng là \(8\)).