Неубывающая необходимость
Дан массив из
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