题目描述
给定 $n$ 个正整数 $a_1,a_2,\cdots, a_n$，这些正整数可以组成 $2^{n}-1$ 个集合（不算空集）。注意，这里的集合允许有相同的元素。分别计算这些集合的元素之和，请你从这些集合的和中，找到它们的中位数（排序后名次恰好在中间的数字）。
例如对于 $2,3,3$ 来说，可以组成的子集有
$$\{2\}, \{3\}, \{3\}, \{2,3\}, \{2,3\}, \{3,3\}, \{2,3,3\}$$
它们的和分别为
$$2, 3, 3, 5, 5, 6, 8$$
中位数是 $5$。
输入
第一行：单个正整数 $n$；
第二行：$n$ 个正整数 $a_1,\dots,a_n$。
输出
单个整数：表示这些集合之和的中位数。
样例输入输出
提示
+ $1\leq a_i\leq 2500$；
+ 对于 $20\%$ 的数据，$1\leq n\leq 10$；
+ 对于 $40\%$ 的数据，$1\leq n\leq 20$；
+ 对于 $70\%$ 的数据，$1\leq n\leq 500$；
+ 对于 $100\%$ 的数据，$1\leq n\leq 1500$。