You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

​【​​题目​描述】

佩奇和乔治在街上捡到了恶魔掉的n张钞票，他们准备这些将钞票平分。他们想得到相同的金额。但是有时候，无论怎么分都无法平均分配，总会剩下一部分。

现在，他们已经​尽可能的分配更多的钱​，然而剩余的部分钞票没有办法平分了，他们又不想将剩下的部分钞票留在街上，他们决定去附近的赌场将剩下的钞票押上，希望得到两倍的赌注。幸运的是真的实现了，有了这些赌注，佩奇和乔治就可以平分了所有钞票。

现在请问，他们每人获得了多少钱。

【​​数据​输入】

第一行一个整数n，表示钞票的数量。

接下n行每行输入1个整数，表示每张钞票的金额。

【​​数据​输出】

一个整数，表示最后每人获得的金额.

【输入样例​​1​】

4
2
3
1
6

【输出样例​​1​】

6

​【​​​样例1解释​】

佩奇拿走金额为6的钞票，乔治拿走金额为6的钞票。

【输入样例2】

5
2
3
5
8
13

【输出样例2】

18

【样例2解释】

佩奇拿走金额5，8的钞票，乔治拿走金额13的钞票。剩下的钞票金额为，用剩下的金额在赌场翻倍。他们每个人的总收入为13+5.

【数据说明】

对于 50% 的数据，满足 n ≤ 13；

对于 70% 的数据，满足 n ≤ 50，钞票总金额不超过10​^3​；

对于 100% 的数据，满足 n ≤ 500 , 钞票总金额不超过10​^5。