Inviting the Village Chief

Interview

Time limit1sMemory limit128 MB

Summary

Plant one tree per day in the best order and report the earliest day after all trees have finished growing.

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

Problem

Farmer Sanggeun bought $N$ tree saplings to plant in his yard. Planting one sapling takes a full day, and he knows exactly how many days each sapling needs before it is fully grown.

Sanggeun wants to invite the village chief over and show off the trees he planted. He will not let the chief down, so he waits until every tree has finished growing. He invites the chief on the day after the last tree is fully grown.

Sanggeun plants one sapling per day starting on day 1, and he may choose the planting order however he likes. A sapling planted on day $k$ that needs $t$ days to grow is fully grown on day $k + t$ .

He picks the order that lets him invite the chief as early as possible. Which day does he invite him?

Input

The input has two lines. The first line has the number of saplings $N$ ( $1 \le N \le 100{,}000$ ). The second line has $t_1, t_2, \dots, t_N$ ( $1 \le t_i \le 1{,}000{,}000$ ) separated by spaces, where $t_i$ is the number of days the $i$ -th sapling needs to grow.

Output

Print the earliest day on which Sanggeun can invite the village chief. The day he bought the saplings is day 1.

Examples2

Example 1
Input
```
4
2 3 4 3
```
Expected output
```
7
```
Example 2
Input
```
6
39 38 9 35 39 20
```
Expected output
```
42
```