Tuấn là một ông chủ bida nổi tiếng nhưng đang trên bờ vực phá sản do làm ăn thua lỗ và phải bán toàn bộ ~n~ bàn bida cao cấp. Anh muốn chia các bàn thành hai phần để bán cho hai người bạn thân là Khôi và Hưng. Là người trọng nghĩa khí, Minh muốn việc chia này công bằng nhất có thể, tức là chênh lệch tổng giá trị giữa hai phần chia là nhỏ nhất.

Yêu cầu: Hãy tính toán chênh lệch tối thiểu đó.

Input

• Dòng đầu tiên chứa số nguyên dương ~n~ ~(1 \le n \le 38)~.

• Dòng tiếp theo chứa ~n~ số nguyên dương ~a_1, a_2, \dots, a_n~ ~(1 \le a_i \le 10^9, i = 1 \dots n)~.

Các số trên một dòng của input file được ghi cách nhau bởi dấu cách.

Output

Ghi một số duy nhất là chênh lệch nhỏ nhất có thể.

Scoring

Sample Input 1

5
13 5 1 5 20

Sample Output 1

2

Notes

Cách chia các bàn tối ưu nhất như sau:

• Hưng nhận các bàn có giá trị ~(13; 5; 5)~ với tổng là ~23~.

• Khôi nhận các bàn có giá trị ~(1; 20)~ với tổng là ~21~.

Khi đó, chênh lệch giữa hai phần là ~2~.