题意

给你 $N$ 个整数 $A_1,A_2,\cdots,A_N$。

考虑所有 $A$ 的非空子序列的和，共有 $2^N-1$ 个这样的和，$2^N-1$ 是一个奇数。

我们将这些和按不降的顺序排序得到 $S_1,S_2,\cdots,S_{2^N-1}$。

求 $S$ 的中位数，即 $S_{2^{N-1}}$。

输入格式

第一行一个整数 $N$。

第二行 $N$ 个整数 $A_1,A_2,\cdots,A_N$。

输出格式

输出一行一个整数，表示 $A$ 的所有非空子序列的和排序得到的数列的中位数。

输入输出样例 #1

输入 #1

3
1 2 1

输出 #1

2

输入输出样例 #2

输入 #2

1
58

输出 #2

58

数据范围

样例 1 解释

此时 $S=(1,1,2,2,3,3,4)$，中位数为 $S_4=2$。

样例 2 解释

此时 $S=(58)$。

限制条件

对于所有的测试点

• $1\le N\le 2000$
• $1\le A_i\le 2000$
• 所有输入均为整数。

性质 $A$，保证 $\sum_{i=1}^{n} A_i \le 10000$