The easy version of this problem differs only in constriction.

Before you start to read the problem, I have to say ARPA is some kind of man, don’t mind ; )

Anyone knows that Arpa is a good ARPA (you see, it isn’t obvious fact at all :P).

There are n other ARPAs with Arpa in the ARPA liberation campaign. They want to play a game (not all ARPAs play at their workplace but Arpa do :P). Every ARPA has a weight (you will say: Oh my god !!).

Arpa can choose some subset of this n ARPAs and sum their weight up, he calls the number of distinct integers that can be made by this way as NOSS (number of subset sums).

For example NOSS of set {17, 23, 40} is 7 : {0, 17, 23, 40, 57, 63, 80}.

Arpa can change weight of one of them to any positive integer (in the same way that he can observe the legal distance with AmirAz).

Now Arpa wonders, what is the maximum NOSS of set of weight of ARPAs can be reached with changing weight of exactly one of ARPAs.

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