Finding Forks

Time limit1sMemory limit1024 MB

Summary

Given the number of forks of each type left in the drawer, find the fewest forks that could have been in the dishwasher to leave two places empty.

Level: Easy3 of 10
Topics: Sorting, Implementation
Solved: No attempts yet

Problem

Your cutlery drawer contains many types of forks. Each has its own purpose and its own place in the drawer. After a dinner 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! 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.

Examples2

Example 1
Input
```
3
4 9 5
```
Expected output
```
9
```

Example 2

Input

10
18 39 5 12 1000000000 54 23 11 123 31415

Expected output