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