As a summer gift, Fiona receives ~N~ flower seeds. She decides to plant them such that each seed has its own pot. She then lines the pots up in a line. Each day, one of the flowers naturally grows by ~1~ cm. The rest of the flowers remain the same height. Initially, all flowers start at a height of ~0~. By the end of the summer, Fiona wants the ~i^{th}~ flower pot to contain a flower of exactly height ~a_i~ cm. However, she is impatient, and wants them to grow up as fast as possible. Each day, Fiona can also artificially increase the heights of some of the flowers by ~1~ (she has magic powers).

If the flowers naturally grow optimally, what is the minimum amount of days Fiona has to wait before the ~i^{th}~ pot contains a flower of height ~a_i~?

Constraints

~1 \le N \le 2 \times 10^5~

~1 \le a_i \le 10^9~

Input Specification

The first line contains a single integer ~N~.

The second line contains ~N~ single space-separated integers, the ~i^{th}~ being ~a_i~.

Output Specification

Output a single integer, the minimum amount of days Fiona has to wait for the plants to be of desired heights.

Sample Input

5
3 5 6 2 4

Sample Output

4

Sample Explanation

After day one, Fiona's plants look like ~[1, 2, 1, 1, 1]~.

After day two, Fiona's plants look like ~[2, 3, 3, 2, 2]~.

After day three, Fiona's plants look like ~[3, 5, 4, 2, 3]~.

After day four, Fiona's plants look like ~[3, 5, 6, 2, 4]~.

Note that there may be other ways to reach the same arrangement in the same amount of days.