Loading [MathJax]/jax/output/HTML-CSS/fonts/TeX/fontdata.js

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 таким образом, что p1<p2<⋯<pn).

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

Первая строка содержит одно целое число t (1≤t≤104) — количество наборов входных данных.

Первая строка каждого набора содержит одно целое число n (1≤n≤2⋅105) — размер перестановки.

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

Сумма n по всем наборам входных данных не превосходит 2⋅105.

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

Для каждого набора выходных данных выведите одно целое число — минимальное количество вышеописанных операций, позволяющих отсортировать перестановку 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].