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

Дана перестановка$$$^{\dagger}$$$ $$$p_1, p_2, \ldots, p_n$$$ целых чисел от $$$1$$$ до $$$n$$$.

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

  • выбрать произвольное $$$x$$$ ($$$2 \le x \le n$$$);
  • создать новую перестановку так:
    • сначала выписать все элементы $$$p$$$, значения которых меньше $$$x$$$, без изменения их порядка;
    • затем выписать все элементы $$$p$$$, значения которых больше или равны $$$x$$$, без изменения их порядка;
  • заменить $$$p$$$ этой полученной перестановкой.

Например, если изначально перестановка была $$$[6, 4, 3, 5, 2, 1]$$$ и выбрано $$$x = 4$$$, то сначала нужно выписать $$$[3, 2, 1]$$$, затем справа дописать $$$[6, 4, 5]$$$. Так, изначальная перестановка будет заменена на $$$[3, 2, 1, 6, 4, 5]$$$.

Найдите наименьшее число операций, необходимое для того, чтобы достичь равенства $$$p_i = i$$$ для всех $$$i = 1, 2, \ldots, n$$$. Можно показать, что ответ всегда существует.

$$$^{\dagger}$$$ Перестановкой длины $$$n$$$ является массив, состоящий из $$$n$$$ различных целых чисел от $$$1$$$ до $$$n$$$ в произвольном порядке. Например, $$$[2,3,1,5,4]$$$ — перестановка, но $$$[1,2,2]$$$ не перестановка ($$$2$$$ встречается в массиве дважды) и $$$[1,3,4]$$$ тоже не перестановка ($$$n=3$$$, но в массиве встречается $$$4$$$).

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

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

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 100\,000$$$).

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \le p_i \le n$$$). Гарантируется, что $$$p_1, p_2, \ldots, p_n$$$ является перестановкой.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$100\,000$$$.

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

Для каждого набора входных данных выведите ответ на отдельной строке.

Пример
Входные данные
5
1
1
2
2 1
6
6 4 3 5 2 1
3
3 1 2
19
10 19 7 1 17 11 8 5 12 9 4 18 14 2 6 15 3 16 13
Выходные данные
0
1
4
1
7
Примечание

В первом наборе входных данных $$$n = 1$$$ и $$$p_1 = 1$$$, так что делать нечего.

Во втором наборе входных данных можно выбрать $$$x = 2$$$, и мы сразу получим $$$p_1 = 1$$$, $$$p_2 = 2$$$.

В третьем наборе входных данных кратчайшей последовательностью операций является, например, следующая:

  1. $$$x = 4$$$: $$$[6, 4, 3, 5, 2, 1] \rightarrow [3, 2, 1, 6, 4, 5]$$$;
  2. $$$x = 6$$$: $$$[3, 2, 1, 6, 4, 5] \rightarrow [3, 2, 1, 4, 5, 6]$$$;
  3. $$$x = 3$$$: $$$[3, 2, 1, 4, 5, 6] \rightarrow [2, 1, 3, 4, 5, 6]$$$;
  4. $$$x = 2$$$: $$$[2, 1, 3, 4, 5, 6] \rightarrow [1, 2, 3, 4, 5, 6]$$$.