시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB259947.368%

문제

To celebrate Children's Day a mother of three brothers - Anton, Dmytro and Borys - gave them loads of sweets. The treats are packed in n boxes, there are ai sweets in the i-th box. The brothers want to share the boxes justly. They agreed to the following rules:

  • an older brother cannot receive more sweets in total than a younger one (Anton is older than Dmytro, and Dmytro is older than Borys),
  • the difference between the total number of sweets given to Anton and the total number of sweets given to Borys should be minimal.

입력

In the first line of the standard input there is an integer n (3 ≤ n ≤ 24), denoting the number of boxes. The second line consists of n positive integers ai (1 ≤ ai ≤ 1,000,000,000), denoting the number of sweets in the boxes.

출력

In the only line of standard output you should write one integer - the difference between the numbers of sweets given to Anton and Borys.

예제 입력 1

4
5 4 7 6

예제 출력 1

3