Вам задан массив \(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\) из него с помощью следующей последовательности операций:
- возьмем первый элемент из \(b\), тогда \(b = [2, 3, 4, 4, 2, 1]\), \(c = [1]\);
- возьмем последний элемент из \(b\), тогда \(b = [2, 3, 4, 4, 2]\), \(c = [1, 1]\);
- возьмем последний элемент из \(b\), тогда \(b = [2, 3, 4, 4]\), \(c = [1, 1, 2]\);
- возьмем первый элемент из \(b\), тогда \(b = [3, 4, 4]\), \(c = [1, 1, 2, 2]\);
- возьмем первый элемент из \(b\), тогда \(b = [4, 4]\), \(c = [1, 1, 2, 2, 3]\);
- возьмем последний элемент из \(b\), тогда \(b = [4]\), \(c = [1, 1, 2, 2, 3, 4]\);
- возьмем единственный элемент из \(b\), тогда \(b = []\), \(c = [1, 1, 2, 2, 3, 4, 4]\) — и массив \(c\) является неубывающим.
Заметьте, что массив, состоящий из одного элемента считается хорошим.
Выведите длину кратчайшего префикса \(a\), который необходимо удалить для того, чтобы сделать \(a\) хорошим массивом. Заметьте, что необходимая длина может быть равна \(0\).
Вам нужно ответить на \(t\) независимых наборов тестовых данных.
Примечание
В первом наборе тестовых данных примера массив \(a\) уже является хорошим, поэтому нам нет необходимости удалять какой-либо префикс.
Во втором наборе тестовых данных примера изначальный массив \(a\) не является хорошим. Давайте удалим первые \(4\) элемента \(a\), результат будет равен \([4, 5, 2]\). Получившийся массив является хорошим. Вы можете доказать, что если удалить меньшее количество первых элементов, результат не будет хорошим.