B. Approval of Requests
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Vladimir Borisovich works as a manager in a very large company. One of his duties is the review and approval of requests submitted by employees through a special information system. Vladimir Borisovich approves requests of different types: there are $$$n$$$ types of requests in total. He opened the application for approving requests and saw that there are $$$a_1$$$ requests of the first type, $$$a_2$$$ of the second type, and so on.

The approval process works as follows: requests are marked with checkboxes, and the "Approve" button is pressed. This button only works when all marked requests are of the same type, meaning that it is not possible to approve several requests of different types at the same time. Approved requests disappear from the list of requests. By pressing the checkbox button next to a request, it can be marked or unmarked. There is also a "Mark All" button that marks all requests at once.

What is the minimum number of button presses in the application that Vladimir Borisovich needs to approve all requests?

Input

The first line of input contains the number $$$n$$$ — the number of types of requests ($$$1 \leq n \leq 10^5$$$). The following $$$n$$$ lines each contain one number: $$$a_1, a_2, a_3$$$, and so on — the number of requests received for each type ($$$1 \leq a_i \leq 10^4$$$ for all $$$i$$$).

Output

The program should output a single number — the minimum possible number of button presses required to approve all requests.

Scoring

Solutions that work correctly under the additional constraint $$$n \leq 1000$$$ will score at least 70 points.

Examples
Input
2
3
2
Output
5
Input
3
1
1
1
Output
6
Note

Explanation of the Example

In the first example, the most advantageous approach is to first mark two requests of the second type and press the "Approve" button, which takes a total of three button presses. After that, press the "Mark All" button and then the "Approve" button again, spending two more presses, thus approving all requests using a total of five button presses. It is not difficult to verify that any other method of approval requires more button presses.