A. Пенчик и современная статуя
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Среди небоскребов в шумном городе Манила только что завершилось строительство самого современного на Филиппинах торгового центра Нойф! Руководитель Пенчик заказал строительство ультрасовременной статуи с $$$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$$$.

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

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

Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 1000$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \leq n \leq 50$$$) — количество колонн.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$h_1, h_2, \ldots, h_n$$$ ($$$1 \le h_i \le n$$$ и $$$h_i\ge h_{i+1}$$$) — высоты колонн.

Обратите внимание, что данный массив $$$h$$$ является невозрастающим.

Заметим, что на сумму $$$n$$$ по всем наборам входных данных не накладываются дополнительные ограничения.

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

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

Пример
Входные данные
3
5
5 4 3 2 1
3
2 2 1
1
1
Выходные данные
4
1
0
Примечание

В первом наборе входных данных начальные высоты колонн равны $$$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$$$.

В третьем наборе входных данных высоты колонн уже являются неубывающими, поэтому никаких операций не требуется.