403386: GYM101149 A Balls in Urn

Sergey takes part in a TV show «Battle of Prophets», in another episode of which the task of the participants is guessing the colors of the balls taken by the show host out of the opaque urn. Using a spirit ritual he found out that the urn contains balls of n different colors, and the number of balls of the i-th color is exactly a_i. The show host is planning to take out balls one by one until the urn becomes empty, and Sergey will have to say the ball's color every time before it is taken out. Unfortunately, the ancient spirits refuse to help him, and he has to trust his intuition only. Sergey wants to guess the color of as many balls as possible in the worst case and is now thinking how many times he is able to make a correct guess for sure.

The first line contains a single integer n (1 ≤ n ≤ 2·10⁵) — the number of different colors.

The second line contains n space-separated integers: a_i (1 ≤ a_i ≤ 10⁹) — the number of balls of the i-th color in the urn.

Output a single integer — the maximal number of balls whose color Sergey can definitely guess.

4
5 2 2 9

9

3
1 2 1

2