Cho mảng A gồm N số nguyên dương. Hãy chia mảng thành hai phần (mỗi phần tử thuộc đúng một phần) sao cho chênh lệch tổng giữa hai phần là nhỏ nhất.

Sử dụng kỹ thuật Meet in the Middle: chia mảng làm 2 nửa, sinh tất cả tổng tập con của mỗi nửa, sắp xếp và tìm tổng gần với tổng/2 nhất.

Đầu vào

• Dòng đầu tiên chứa số nguyên N (\(1 \le N \le 40\)).
• Dòng thứ hai chứa N số nguyên dương \(A_i\) (\(1 \le A_i \le 10^15\)).

Đầu ra

Chênh lệch nhỏ nhất có thể.

Ví dụ

Input:
5
1 2 3 4 5

Output:
1

Giải thích

Chia {1, 2, 5} và {3, 4}: tổng 8 và 7, chênh lệch 1.

Ràng buộc & Subtasks