Незростаюча послідовність

Обмеження: 2 сек., 256 МіБ

Зеник виконав чергову забаганку Марічки — виписав послідовність із \(n\) чисел \(a_1\), \(a_2\), ..., \(a_n\). Як Марічка і хотіла, числа у цій послідовності утворюють неспадну послідовність, тобто кожен наступний елемент є більшим або рівним за попередній. Щасливий Зеник побіг до своєї Марічки дарувати їй цю послідовність.

Аж раптом, Зеника охопив холодний піт. У його душі все зупинилось. Він згадав, що Марічка хотіла отримати незростаючу послідовніть, а не неспадну. Тобто, у його послідовності кожен наступний елемент має бути меншим або рівним за попередній. Тепер Зеник хоче якомога швидше виправити свою помилку. За одну хвилину, Зеник може вибрати довільне число із поточної послідовності та замінити його значення на довільне інше. За яку мінімальну кількість часу Зеник може виправити свою помилку?

Вхідні дані

У першому рядку задано одне ціле число \(n\) — кількість елементів у послідовності.

У другому рядку задано неспадну послідовність \(a_1\), \(a_2\), ..., \(a_n\).

Вихідні дані

У єдиному рядку виведіть одне ціле число — мінімальну кількість хвилин, за яку Зеник може змінити послідовність на незростаючу.

Обмеження

\(1 \le n \le 10^5\),

\(0 \le a_i \le 10^9\),

\(a_{i+1} \ge a_i\),

для 40% тестів виконується додаткове обмеження: \(n, a_i \le 10^3\).

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
4 1 4 4 7	2

Примітки

У прикладі можна замінити два елементи: перший числом 7, останній числом 2. Утвориться послідовність [7, 4, 4, 2], яка є незростаючою.