Мама подарила Васе последовательность целых чисел длины n. Он выбирает произвольный элемент последовательности и прибавляет к нему или вычитает из него число, не превышающее k. Эту операцию над произвольным элементом последовательности он может произвести не более одного раза. Васе стало интересно: какое минимальное число k нужно выбрать, чтобы из заданной последовательности при помощи операций сложения и вычитания образовалась строго возростающая последовательность натуральных чисел.

Входные данные

В первой строке задано целое число n (1 < n ≤ 105), в следующей строке задано n чисел, не превышающих 2 ·109.

Выходные данные

Выведите число k.