Среди небоскребов в шумном городе Манила только что завершилось строительство самого современного на Филиппинах торгового центра Нойф! Руководитель Пенчик заказал строительство ультрасовременной статуи с \(n\) колоннами.
Высоты колонн статуи можно представить в виде массива \(h\) из \(n\) целых положительных чисел, где \(h_i\) — высота \(i\)-й колонны для всех \(i\) от \(1\) до \(n\).
Пенчик хочет, чтобы высоты колонн шли в неубывающем порядке, то есть выполнялось \(h_i \le h_{i + 1}\) для всех \(i\) от \(1\) до \(n - 1\). Однако из-за путаницы памятник был построен так, что высоты колонн находятся в невозрастающем порядке, то есть \(h_i \ge h_{i + 1}\) для всех \(i\) от \(1\) до \(n - 1\).
К счастью, Пенчик может модифицировать памятник и проделать следующую операцию над колоннами столько раз, сколько потребуется:
- Сделать высоту колонны равной любому целому положительному числу. Формально, выбрать индекс \(1\le i\le n\) и положительное целое число \(x\), а затем присвоить \(h_i := x\).
Помогите Пенчику определить минимальное количество операций, необходимых для того, чтобы высота колонн памятника неубывала.
Выходные данные
Для каждого набора входных данных выведите одно целое число, представляющее собой минимальное количество операций, необходимых для того, чтобы высота колонн неубывала.
Примечание
В первом наборе входных данных начальные высоты колонн равны \(h = [5, 4, 3, 2, 1]\).
- В первой операции Пенчик изменяет высоту колонны \(1\): \(h_1 := 2\).
- Во второй операции он изменяет высоту колонны \(2\): \(h_2 := 2\).
- В третьей операции он изменяет высоту колонны \(4\): \(h_4 := 4\).
- В четвертой операции он изменяет высоту колонны \(5\): \(h_5 := 4\).
После этих операций высоты колонн \(h = [2, 2, 3, 4, 4]\), то есть они неубывают. Можно доказать, что Пенчик не может сделать высоты колонн неубывающими менее чем за \(4\) операции.
Во втором наборе входных данных Пенчик может сделать высоты колонн неубывающими, сделав высоту колонны \(3\) равной \(h_3 := 2\).
В третьем наборе входных данных высоты колонн уже являются неубывающими, поэтому никаких операций не требуется.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
5
5 4 3 2 1
3
2 2 1
1
1
|
4
1
0
|