Eastern Express Cars

Interview

Time limit2sMemory limit1024 MB

Summary

Given passenger counts in n cars, find the minimum time to unload everyone when one step empties a car or removes one passenger from each nonempty car.

Level: Medium5 of 10
Topics: Greedy, Sorting
Solved: No attempts yet

Statement

A train runs from Istanbul to London with $n$ cars. Car $i$ holds $a_i$ passengers, and all of them want to get off at the final stop, Victoria Station in London. The train has many cars and many passengers, so the crew needs a plan for unloading them.

In one unit of time, the conductor can do one of two things. The conductor can empty an entire car, or let one passenger out of every car that still has passengers.

The passengers are in a hurry and the conductor is in a panic. Find the minimum time needed to unload all passengers from the train.

Input

The first line contains one integer $n$ , the number of cars $(1 \leq n \leq 10^5)$ .

The second line contains $n$ integers $a_i$ $(0 \leq a_i \leq 10^9)$ , where $a_i$ is the number of passengers in the $i$ -th car.

Output

Print one integer, the minimum time needed to unload all passengers.

Examples2

Example 1
Input
```
3
1 1 2
```
Expected output
```
2
```
Example 2
Input
```
5
10 20 100 100 100
```
Expected output
```
5
```