题目描述

本题来自 AGC 020 Median Sum。

一个可重集由 $N$ 个整数组成，请求出它的非空子集和的中位数。

输入格式

第一行为一个整数 $N$。

接下来一行 $N$ 个整数 $a_i$，描述可重集。

输出格式

输出一行一个整数，表示答案。

样例

3
1 2 1

2

1
58

58

数据范围

对于全部数据，$1\le N,a_i\le 2\times 10^3$。