Неубывающая необходимость

Дан массив из n целых чисел. Нужно сделать этот массив неубывающим, выполняя следующую операцию некоторое количество раз (включая возможность не выполнять её вовсе):

Выберите любой индекс i (1 ≤ ≤ n) и замените на любое целое число.

Ваша задача — свести к минимуму количество таких операций, необходимых для преобразования массива в неубывающий.

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

В первой строке содержится одно целое число n (1 ≤ n ≤ 100 000), обозначающее длину массива.

Во второй строке записаны n целых чисел , разделённых пробелами (1 ≤ ).

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

Программа должна вывести одно целое число — минимальное количество операций, необходимых, чтобы сделать массив неубывающим.

Примеры

Ввод

Результат

7
1 3 2 2 7 4 3

3

4
1 2 1 4

1

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue