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

Вхідні дані

У першому рядку задано ціле число n (1 < n ≤ 105), у наступному рядку задано n чисел, що не перевищують 2 ·109.

Вихідні дані

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