Vasylko and the Sequence#3538
Mom gave Vasyl a sequence of integers of length . Vasyl can choose any element of the sequence and either add or subtract a number not greater than from it. He can perform this operation on each element of the sequence at most once. Vasyl wants to know the smallest number that allows the sequence to be transformed into a strictly increasing sequence of natural numbers using these operations.
The first line contains an integer (1 < n \le 10^5), and the second line contains integers, each not exceeding 2 \cdot 10^9.
Output the minimum number .
Example 1