This year, Ivan finishes school and enters the university. During his studies, he often participated in computer science olympiads and he has accumulated many diplomas. Ivan laid out diplomas in folders completely haphazardly, that is, any diploma could end up in any of the folders. Fortunately, Ivan remembers how many diplomas are in each of the folders.
Ivan wants to bring a folder containing the diploma of the Moscow Olympiad in programming to the admission committee of the selected university (Ivan has exactly one such diploma). In order to understand that this folder does not contain the desired diploma, Ivan needs to look through all the diplomas from this folder. To open one folder, Ivan needs to spend one second, viewing one diploma also takes him one second, and he can instantly move to the next folder after finishing viewing the previous one. Ivan can choose the order of viewing folders. The fact that you can not look for a diploma in empty folders is obvious to Ivan.
Given the number of diplomas in each of the folders, it is required to determine the shortest time in which, in the worst case, Ivan will understand which folder contains the diploma he needs.
Input
The first line of the input file contains an integer N (1 ≤ N ≤ 10
5) - the number of folders. The second line contains N integers a
1, a
2, ..., a
N (0 ≤ a
i< /sub> ≤ 105) - number of diplomas in each folder.
Imprint
Print a single number - the minimum number of seconds Ivan needs in the worst case to determine which folder contains the diploma.
Note
In the first example, Ivan can open and view folder 2 in 2 seconds and, not finding a diploma there, realize that the diploma is in folder 1.
In the second example, Ivan will look through folder 1 in 2 seconds, then in 2 seconds he will look through folder 4, and if there is no diploma in any of them, he will understand that the diploma is in folder 3.
Examples
| # |
Input |
Output |
| 1 |
2
2 1
| 2 |
| 2 |
4
1 0 2 1
| 4 |