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