C. Сделай хорошо
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам задан массив $$$a$$$, состоящий из $$$n$$$ целых чисел. Вам нужно найти длину наименьшего (кратчайшего) префикса элементов, которые вам нужно удалить из $$$a$$$, чтобы сделать его хорошим массивом. Напомним, что префиксом массива $$$a=[a_1, a_2, \dots, a_n]$$$ называется подмассив, состоящий из первых нескольких элементов: префикс массива $$$a$$$ длины $$$k$$$ — это массив $$$[a_1, a_2, \dots, a_k]$$$ ($$$0 \le k \le n$$$).

Массив $$$b$$$ длины $$$m$$$ называется хорошим, если вы можете получить из него неубывающий массив $$$c$$$ ($$$c_1 \le c_2 \le \dots \le c_{m}$$$), повторяя следующую операцию $$$m$$$ раз (изначально массив $$$c$$$ пустой):

  • выбрать первый или последний элемент в $$$b$$$, удалить его из $$$b$$$ и добавить его в конец массива $$$c$$$.

Например, если делаем $$$4$$$ операции: возьмем $$$b_1$$$, затем $$$b_{m}$$$, затем $$$b_{m-1}$$$ и в конце $$$b_2$$$, то $$$b$$$ становится $$$[b_3, b_4, \dots, b_{m-3}]$$$ и $$$c =[b_1, b_{m}, b_{m-1}, b_2]$$$.

Рассмотрим следующий пример: $$$b = [1, 2, 3, 4, 4, 2, 1]$$$. Этот массив хороший, потому что мы можем получить неубывающий массив $$$c$$$ из него с помощью следующей последовательности операций:

  1. возьмем первый элемент из $$$b$$$, тогда $$$b = [2, 3, 4, 4, 2, 1]$$$, $$$c = [1]$$$;
  2. возьмем последний элемент из $$$b$$$, тогда $$$b = [2, 3, 4, 4, 2]$$$, $$$c = [1, 1]$$$;
  3. возьмем последний элемент из $$$b$$$, тогда $$$b = [2, 3, 4, 4]$$$, $$$c = [1, 1, 2]$$$;
  4. возьмем первый элемент из $$$b$$$, тогда $$$b = [3, 4, 4]$$$, $$$c = [1, 1, 2, 2]$$$;
  5. возьмем первый элемент из $$$b$$$, тогда $$$b = [4, 4]$$$, $$$c = [1, 1, 2, 2, 3]$$$;
  6. возьмем последний элемент из $$$b$$$, тогда $$$b = [4]$$$, $$$c = [1, 1, 2, 2, 3, 4]$$$;
  7. возьмем единственный элемент из $$$b$$$, тогда $$$b = []$$$, $$$c = [1, 1, 2, 2, 3, 4, 4]$$$ — и массив $$$c$$$ является неубывающим.

Заметьте, что массив, состоящий из одного элемента считается хорошим.

Выведите длину кратчайшего префикса $$$a$$$, который необходимо удалить для того, чтобы сделать $$$a$$$ хорошим массивом. Заметьте, что необходимая длина может быть равна $$$0$$$.

Вам нужно ответить на $$$t$$$ независимых наборов тестовых данных.

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

Первая строка теста содержит одно целое число $$$t$$$ ($$$1 \le t \le 2 \cdot 10^4$$$) — количество наборов тестовых данных. Затем следуют $$$t$$$ наборов тестовых данных.

Первая строка набора тестовых данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — длину $$$a$$$. Вторая строка набора тестовых данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 2 \cdot 10^5$$$), где $$$a_i$$$ — $$$i$$$-й элемент в $$$a$$$.

Гарантируется, что сумма всех $$$n$$$ не превосходит $$$2 \cdot 10^5$$$ ($$$\sum n \le 2 \cdot 10^5$$$).

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

Для каждого набора тестовых данных выведите ответ на него: длину кратчайшего префикса элементов, которые нужно удалить из $$$a$$$, чтобы он стал хорошим массивом.

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

В первом наборе тестовых данных примера массив $$$a$$$ уже является хорошим, поэтому нам нет необходимости удалять какой-либо префикс.

Во втором наборе тестовых данных примера изначальный массив $$$a$$$ не является хорошим. Давайте удалим первые $$$4$$$ элемента $$$a$$$, результат будет равен $$$[4, 5, 2]$$$. Получившийся массив является хорошим. Вы можете доказать, что если удалить меньшее количество первых элементов, результат не будет хорошим.