Vasylko and the Sequence

Mom gave Vasyl a sequence of integers of length n. Vasyl can choose any element of the sequence and either add or subtract a number not greater than k from it. He can perform this operation on each element of the sequence at most once. Vasyl wants to know the smallest number k that allows the sequence to be transformed into a strictly increasing sequence of natural numbers using these operations.

Input

The first line contains an integer n (1 < n ≤ 10^5), and the second line contains n integers, each not exceeding 2 · 10^9.

Output

Output the minimum number k.

Examples