分数：$700$ 分

问题描述

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

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

将这些和按非递减顺序排列为 $S_1, S_2, \cdots, S_{2^N - 1}$。

找到这个列表的中位数，即 $S_{2^{N-1}}$。

约束条件

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

输入

从标准输入中读取，格式如下：

$N$

$A_1$ $A_2$ $...$ $A_N$

输出

打印所有非空子序列和的排序列表的中位数。

3
1 2 1

2

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

1
58

58

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