Có n quả táo với khối lượng đã biết. Nhiệm vụ của bạn là chia táo thành hai nhóm sao cho sự khác biệt giữa trọng lượng của 2 nhóm là nhỏ nhất.

Đầu vào: Dòng 1 là số nguyên dương N là số lượng quả táo. Dòng thứ 2 là N số nguyên p1,p2...,.pn là trọng lượng tương ứng của các quả táo.

1<=N<=20; 1<=pi<=10^9;

Đầu ra: In ra độ chênh lệch nhỏ nhất giữa 2 nhóm táo.

Input

5
3 2 7 4 1

Output:

1