Мама подарила Васе последовательность целых чисел длины n. Он выбирает произвольный элемент последовательности и прибавляет к нему или вычитает из него число, не превышающее k. Эту операцию над произвольным элементом последовательности он может произвести не более одного раза. Васе стало интересно: какое минимальное число k нужно выбрать, чтобы из заданной последовательности при помощи операций сложения и вычитания образовалась строго возростающая последовательность натуральных чисел.
В первой строке задано целое число n (1 < n ≤ 10^5
), в следующей строке задано n чисел, не превышающих 2 ·10^9
.
Выведите число k.