403386: GYM101149 A Balls in Urn

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

A. Balls in Urntime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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 ai. 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.

Input

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

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

Output

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

ExamplesInput
4
5 2 2 9
Output
9
Input
3
1 2 1
Output
2

加入题单

上一题 下一题 算法标签: