ALEKO và OKELA có ~n~ viên kẹo, mỗi viên có độ ngon là ~a_i~ họ muốn chia n viên kẹo ấy thành 2 phần với chênh lệch giữa tổng độ ngon của 2 phần là tối thiểu, hãy tính độ chênh lệch ấy .

INPUT

Đầu vào tiêu chuẩn theo định dạng sau:

~n~ ~(1 \leq n \leq 40 )~

~a_1~ ~a_{2}~ ~a_{3}~ … ~a_{n}~ (1 ~\leq~ ~a_{i}~ ~\leq~ ~10^9~ )

OUTPUT

Một số duy nhất là kết quả của bài toán

Simple Input

4
5 10 4 2

Simple Output

1

Giải thích test đề:

Các viên kẹo sẽ được chia thành [5,4,2] và [10] với độ chênh lệch là 1.

Subtask 1: 20% điểm với ~n~ ~\leq~ ~10~, ~a_i~ ≤ ~10^5~

Subtask 2: 40% điểm với ~n~ ~\leq~ ~20~, ~a_i~ ~\leq~ ~10^5~

Subtask 3: 40% điểm với ~n~ ~\leq~ ~40~, ~a_i~ ~\leq~ ~10^9~

K18 ai giải được tới tìm Ali Vũ sẽ nhận được kẹo :>