问题描述

石老师有 $N$ 个整数 $A_1, A_2, ..., A_N$.

考虑 $A$ 的所有非空子序列的和。 有 $2^N−1$ 个这样的和。

令这些和按非递减顺序排列得到 $S_1, S_2, ..., S_{2^N−1}$。

找到此列表的中位数 $S_{2^{N−1}}$。

• $A$ 的非空子序列 是指从 $A$ 中将一个或多个元素提取出来并不改变相对位置形成的序列。 例如，$A=(1,2,3)$ 的非空子序列有 $(1), (2), (3), (1,2), (1,3), (2,3), (1,2,3)$。

约束

• $1≤N≤2000$
• $1≤A_i≤2000$
• 所有输入值都是整数。

输入

输入以下列格式从标准输入给出：

N
A1 A2 ... AN

输出

输出 $A$ 的所有非空子序列之和的排序列表的中位数。

样例输入 1

3
1 2 1

样例输出 1

2

在这种情况下，$S=(1,1,2,2,3,3,4)$。 它的中位数是 $S_4=2$。

样例输入 2

1
58

样例输出 2

58

在这种情况下，$S=(58)$。