부분 합 나누기

N개의 정수를 두 집합으로 나누어 각 집합의 합의 차이를 최소화하라.

입력

첫째 줄에 N이 주어진다.
둘째 줄에 N개의 정수가 주어진다.

• 1 ≤ N ≤ 20
• 1 ≤ 각 정수 ≤ 100,000

출력

두 집합의 합의 차이의 최솟값을 출력한다.

예제 입력 1

4
1 6 11 5

예제 출력 1

1