题目描述

给定 $n$ 个整数 $a_1,a_2,\cdots, a_n$，这些数可以组成 $2^{n}-1$ 个集合（不算空集）。由于 $a_i$ 可能重复，为方便起见，规定它们组成的集合中允许出现重复的元素。

分别计算每个集合的元素之和，请从中找到这些和的中位数。中位数是指排序后名次恰好在中间的数。

例如对于 $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$。

输出格式

单个整数：表示这些集合之和的中位数。

3
2 3 3

5

1
10

10

数据范围

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