AT_agc020_c.[AGC020C] Median Sum

给你 $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\le N\le 2000$
• $1\le A_i\le 2000$
• 所有输入均为整数。

样例 1 解释

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

样例 2 解释

此时 $S=(58)$。