Gardening on the Train

Interview

Time limit2sMemory limit1024 MB

Summary

Given n plants with growth times a_i, plant one per day to minimize the day when the last plant ripens.

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

Problem

The journey of the Eastern Express is quite long, so the food brought on board is not always enough to feed its passengers. For this reason, vegetables and plants are grown on the train. But before a plant can grow, it must first be planted.

Buk has $n$ plants. The $i$ -th plant needs $a_i$ days to grow and ripen. Buk is very busy and cannot plant more than one plant per day, so the order of planting matters. He wants all plants to ripen as early as possible so they can be used in cooking. Help him find the minimum number of days after which all plants can ripen for some planting order.

Input

The first line contains the number $n$ of plants Buk has ( $1 \le n \le 10^5$ ).

The next line contains $n$ integers $a_i$ , where $a_i$ is the number of days the $i$ -th plant needs to grow and ripen ( $1 \le a_i \le 10^9$ ).

Output

Print a single line with the minimum number of days after which all plants can grow and ripen, for some planting order.

Examples1

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