C. Min Max сортировка
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дана перестановка $$$p$$$ размера $$$n$$$ (перестановка размера $$$n$$$ — это массив размера $$$n$$$, в котором каждое целое число от $$$1$$$ до $$$n$$$ встречается ровно один раз).

Вы можете выполнить следующую операцию любое количество раз (возможно, ноль):

  1. выбрать два различных элемента $$$x$$$ и $$$y$$$ и удалить их из перестановки;
  2. вставить минимум из $$$x$$$ и $$$y$$$ в перестановку таким образом, чтобы он стал первым элементом;
  3. вставить максимум из $$$x$$$ и $$$y$$$ в перестановку таким образом, чтобы он стал последним элементом;

Например, если $$$p = [1, 5, 4, 2, 3]$$$, и мы хотим применить операцию к элементам $$$3$$$ и $$$5$$$, тогда после первого шага операции $$$p = [1, 4, 2]$$$; а после вставки элементов $$$p = [3, 1, 4, 2, 5]$$$.

Ваша задача — определить минимальное количество вышеописанных операций, позволяющих отсортировать перестановку $$$p$$$ в возрастающем порядке (т. е. преобразуйте $$$p$$$ таким образом, что $$$p_1 < p_2 < \dots < p_n$$$).

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

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

Первая строка каждого набора содержит одно целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — размер перестановки.

Вторая строка набора входных данных содержит $$$n$$$ различных целых чисел от $$$1$$$ до $$$n$$$ — заданную перестановку $$$p$$$.

Сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

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

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

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

В первом примере можно действовать следующим образом:

  1. в перестановке $$$p = [1, 5, 4, 2, 3]$$$ выберем элементы $$$4$$$ и $$$2$$$, тогда после применения операции перестановка $$$p = [2, 1, 5, 3, 4]$$$;
  2. в перестановке $$$p = [2, 1, 5, 3, 4]$$$ выберем элементы $$$1$$$ и $$$5$$$, тогда после применения операции перестановка $$$p = [1, 2, 3, 4, 5]$$$.