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