Because of necessary software maintenance, Jutge.org may not work well on the afternoons of the 20th and 21th of april.

Optimal separation P64493

Statement

html

Given n natural numbers, find how to separate them into two sets so that the absolute value of the difference between the sums of the elements of the two sets is minimized.

Input

Input consists of several cases, each with n followed by n natural numbers between 1 and 10⁶. Assume 1 ≤ n ≤ 23.

Output

For every case, print the minimum possible difference.

Public test cases

Input

5   18 10 19 14 3
4   1000 10 10 10
1   20
7   1 2 4 8 16 32 64

Output

Information

Author: Salvador Roura
Language: English
Translator: Salvador Roura
Original language: Catalan
Other languages: Catalan
Official solutions: C++ Python
User solutions: C++