G. Почти возрастающий массив
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Назовем массив почти возрастающим, если можно удалить не более одного элемента таким образом, что массив станет строго возрастающим (то есть, каждый следующий элемент будет строго больше предыдущего).

Задан массив a, состоящий из n элементов. Разрешается заменить элемент на любой позиции на произвольное целое число (эту операцию можно производить произвольное число раз). Какое минимальное количество раз надо проделать данную операцию, чтобы сделать массив почти возрастающим?

Входные данные

В первой строке записано одно целое число n (2 ≤ n ≤ 200000) — количество элементов в a.

Во второй строке записаны n целых чисел a1, a2, ..., an (1 ≤ ai ≤ 109) — массив a.

Выходные данные

Выведите минимальное количество операций по замене элемента, которое необходимо произвести, чтобы сделать a почти возрастающим.

Примеры
Входные данные
5
5 4 3 2 1
Выходные данные
3
Входные данные
5
1 2 8 9 5
Выходные данные
0