描述今天是阴历七月初五，acm队员zb的生日。zb正在和C小加、never在武汉集训。他想给这两位兄弟买点什么庆祝生日，经过调查，zb发现C小加和never都很喜欢吃西瓜，而且一吃就是一堆的那种，zb立刻下定决心买了一堆西瓜。当他准备把西瓜送给C小加和never的时候，遇到了一个难题，never和C小加不在一块住，只能把西瓜分成两堆给他们，为了对每个人都公平，他想让两堆的重量之差最小。每个西瓜的重量已知，你能帮帮他么？
- 输入
-
多组测试数据（<=）。数据以EOF结尾
第一行输入西瓜数量N ( ≤ N ≤ )
第二行有N个数，W1, …, Wn ( ≤ Wi ≤ )分别代表每个西瓜的重量
- 输出
-
- 样例输入
-
- 样例输出
-
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<math.h>
#include<algorithm>
#include<queue>
#include<set>
#include<bitset>
#include<map>
#include<vector>
#include<stdlib.h>
#include <stack>
using namespace std;
#define PI acos(-1.0)
#define max(a,b) (a) > (b) ? (a) : (b)
#define min(a,b) (a) < (b) ? (a) : (b)
#define ll long long
#define eps 1e-10
#define MOD 1000000007
#define N 1000000
#define inf 1e12
int n;
int a[N];
int sum;
int ans;
void dfs(int cur,int num){
if(cur==n){
return;
}
int t=abs(sum-num-num);
if(t<ans){
ans=t;
}
dfs(cur+,num+a[cur]);
dfs(cur+,num);
}
int main()
{
while(scanf("%d",&n)==){
sum=;
for(int i=;i<n;i++){
scanf("%d",&a[i]);
sum+=a[i];
}
ans=inf;
dfs(,);
printf("%d\n",ans);
}
return ;
}