问题描述

给定 $N$ 个整数 $A_1$、$A_2$、...、$A_N$。

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

将这些和按非递减顺序列出，得到列表 $S_1$、$S_2$、...、$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$

输出

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

示例输入 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)$。