An và Bình có ~n~ gói kẹo, gói thứ ~i~ có ~a_i~ cái kẹo. An đề xuất thuật toán chia kẹo như sau:

Ban đầu sắp xếp ~n~ gói kẹo theo một thứ tự, sau đó lần lượt lấy từng gói kẹo theo thứ tự để chia ~n~ gói kẹo thành ~2~ phần. Mỗi lượt, xem phần nào ít hơn thì cho gói kẹo vào phần đó, nếu trong trường hợp hai phần bằng nhau thì cho vào phần thứ nhất. Bình nhận ra ngay việc chia kẹo ảnh hưởng rất nhiều từ thứ tự sắp xếp gói kẹo, do đó Bình đã chọn một thứ tự sắp xếp ~n~ gói kẹo và sẽ lấy phần thứ nhất.

Yêu cầu: Cho ~a_1, a_2, \dots, a_n~ là số lượng kẹo của ~n~ gói. Hãy in ra độ chênh lệch nhỏ nhất trong các cách chia phần.

Input

Vào từ file CANDY.INP:

• Dòng đầu chứa số nguyên ~n\ (n \le 1000)~.
• Dòng thứ hai chứa ~n~ số nguyên dương ~a_1, a_2, \dots, a_n\ (a_i \le 1000)~.

Output

Ghi ra tệp CANDY.OUT:

• Một số nguyên dương là độ chênh lệch nhỏ nhất trong các cách chia phần.

Subtasks

• ~40\%~ test có ~n \le 8~.
• ~30\%~ test có ~n \le 70~.
• ~30\%~ test có ~n \le 1000,\ a_i = i~.

Sample Input 1

3
2 1 3

Sample Output 1

0

Sample Input 2

6
387 944 903 682 450 360

Sample Output 2

868