为了节省开支，圣诞老人开始雇佣驯鹿以外的其他动物，通过短期“零工”合同来拉雪橇。因此，每次行程中用来拉雪橇的动物体型差异可能很大。上周他有 2 只水牛、37 只田鼠和 1 只雪纳瑞。不幸的是，两只水牛都套在了左侧，导致整个雪橇在飞行中因重量不平衡而翻倒。

为了防止此类事故再次发生，圣诞老人需要将某次行程中的动物分成两组，使得一组中所有动物的重量之和等于另一组中所有动物的重量之和。为了使套车过程高效，圣诞老人正在寻找一个整数目标重量 $t$，使得所有重量小于 $t$ 的动物进入一组，而所有重量大于 $t$ 的动物进入另一组。如果存在多个这样的 $t$，他希望找到最小的一个。这里有一个小问题：如果有些动物的重量恰好等于 $t$ 该怎么办？圣诞老人是这样解决的：如果这类动物的数量是偶数，他将它们平均分配到两组中（从而均匀分配重量）。但如果这类动物的数量是奇数，那么其中一只动物会被送去和精灵们一起制作玩具（它不会被放入任何一组），剩下的（现在是偶数个）动物则被平均分配到两组中。

输入格式

输入描述了一份动物重量列表。第一行包含一个整数 $m$ ($2 \le m \le 10^5$)，表示动物的数量。接下来的 $m$ 行，每行包含一个正整数。这些是动物的重量（单位：盎司）。重量超过 $20\,000$ 盎司的动物太大，无法拉动雪橇，因此给出的重量都不会超过这个最大值。

输出格式

输出如上所述的最小整数目标重量 $t$。题目保证一定能找到这样一个整数。

样例

样例输入 1

4
3
6
1
2

样例输出 1

4

样例输入 2

4
11
8
3
10

样例输出 2

10

样例输入 3

2
99
99

样例输出 3

99

Figure 1. Animals used by Santa for his sleigh