시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 11 3 3 42.857%

문제

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