Майже зростаючий масив

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

Дано масив $a$, що складається з $n$ елементів. Дозволяється замінити будь-який елемент на довільне ціле число (цю операцію можна виконувати необмежену кількість разів). Яка мінімальна кількість таких замін потрібна, щоб зробити масив майже зростаючим?

Вхідні дані

У першому рядку подано одне ціле число $n(2\le n\le 2\cdot 10^5)$ — кількість елементів у масиві $a$.

У другому рядку наведено $n$ цілих чисел $a_1,a_2,...,a_n(1\le a_i\le 10^9)$ — елементи масиву $a$.

Вихідні дані

Виведіть мінімальну кількість замін елементів, необхідну для того, щоб масив $a$ став майже зростаючим.

Приклади