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 $a_{i}$ 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.

Input Format

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 $a_{i}$ ($1 ≤ a_{i} ≤ 1\,000\,000\,000$), denoting the number of sweets in the boxes.

Output Format

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

Example

Input

4
5 4 7 6

Output

3