F1. Летающая сортировка (простая версия)
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это простая версия задачи. В этой версии все числа в заданном массиве различны и ограничения на $$$n$$$ меньше, чем в сложной версии задачи.

Вам дан массив $$$a$$$ из $$$n$$$ целых чисел (в массиве нет одинаковых элементов). Вы можете производить над элементами массива следующие операции:

  1. выбрать любой индекс $$$i$$$ ($$$1 \le i \le n$$$) и переместить элемент $$$a[i]$$$ в начало массива;
  2. выбрать любой индекс $$$i$$$ ($$$1 \le i \le n$$$) и переместить элемент $$$a[i]$$$ в конец массива.

Например, если $$$n = 5$$$, $$$a = [4, 7, 2, 3, 9]$$$, то можно применить следующую последовательность операций:

  • после применения операции первого типа ко второму элементу массив $$$a$$$ станет равным $$$[7, 4, 2, 3, 9]$$$;
  • после применения операции второго типа ко второму элементу массив $$$a$$$ станет равным $$$[7, 2, 3, 9, 4]$$$.

Вы можете проводить операции любого типа произвольное количество раз в любом порядке.

Найдите минимальное суммарное количество операций первого и второго типа, которые сделают массив $$$a$$$ отсортированным по неубыванию. Иными словами, сколько минимум операций надо применить, чтобы массив удовлетворял неравенствам $$$a[1] \le a[2] \le \ldots \le a[n]$$$?

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

В первой строке записано одно целое число $$$t$$$ ($$$1 \le t \le 100$$$) — количество наборов тестовых данных в тесте. Далее следуют $$$t$$$ наборов тестовых данных.

Каждый набор начинается со строки, в которой записано целое число $$$n$$$ ($$$1 \le n \le 3000$$$) — размер массива $$$a$$$.

Далее следуют $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 10^9$$$) — массив, который требуется отсортировать заданными операциями. Все числа в заданном массиве различны.

Сумма $$$n$$$ по всем наборам тестовых данных в одном тесте не превосходит $$$3000$$$.

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

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

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

В первом тестовом наборе нужно переместить сначала тройку, а потом двойку в начало массива. Следовательно, искомая последовательность операций может иметь вид: $$$[4, 7, 2, 3, 9] \rightarrow [3, 4, 7, 2, 9] \rightarrow [2, 3, 4, 7, 9]$$$.

Во втором тестовом наборе нужно переместить единицу в начало массива, а восьмерку — в конец. Искомая последовательность операций имеет вид: $$$[3, 5, 8, 1, 7] \rightarrow [1, 3, 5, 8, 7] \rightarrow [1, 3, 5, 7, 8]$$$.

В третьем тестовом наборе массив уже отсортирован.