Input

The first line of input contains one integer n ( n ≤ 17 * 232 ). The second line contains n numbers: a1 , a2, …, an . (0 ≤ ai, (sum of ai) * n ≤ 236).

Output

Print one integer, the maximum NOSS of set of weight of ARPAs can be reached if he acts optimally.

Examples
Input
3
17 23 40
Output
8
Input
3
1 1 1
Output
6
Input
2
1 1
Output
4
Input
3
1 1 2
Output
8