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

Constraints

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

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

Example

5
3 2 7 4 1

1