题目描述

给你 $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

输入

3
1 2 1

输出

2

样例 2

输入

1
58

输出

58

说明/提示

数据范围

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