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)$。