Problem G
Finding Forks
Your cutlery drawer contains many types of forks. Each with their own purpose, and each with its own place in the cutlery drawer. After a nice dining party with all your friends, disaster struck! You put all the used forks in the dishwasher, but now you are unsure where to put back some of the forks, because at least two places in the cutlery drawer are empty! And worse, you do not remember which type of fork belongs where!
What is the minimum number of forks that must have been in the dishwasher to cause this confusion?
Input
The input consists of:
-
One line with an integer $n$ ($2\leq n\leq 10^5$), the number of types of forks.
-
One line with $n$ integers $a$ ($1\leq a \leq 10^9$), the number of forks of each type.
Output
Output the minimum number of forks that must have been in the dishwasher.
| Sample Input 1 | Sample Output 1 |
|---|---|
3 4 9 5 |
9 |
| Sample Input 2 | Sample Output 2 |
|---|---|
10 18 39 5 12 1000000000 54 23 11 123 31415 |
16 |
