C. Увеличения в группах
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дан массив $$$a$$$ длины $$$n$$$. Чтобы вычислить штраф, нужно выполнить следующие действия:

  1. Разбить массив $$$a$$$ на две (возможно, пустых) подпоследовательности $$$^\dagger$$$ $$$s$$$ и $$$t$$$ такие, что каждый элемент $$$a$$$ находится либо в $$$s$$$, либо в $$$t^\ddagger$$$.
  2. Для массива $$$b$$$ длины $$$m$$$ определим штраф $$$p(b)$$$ массива $$$b$$$ как количество индексов $$$i$$$ между $$$1$$$ и $$$m - 1$$$ таких, что $$$b_i < b_{i + 1}$$$.
  3. Общий штраф, который вы получите, равен $$$p(s) + p(t)$$$.

Найдите минимально возможный штраф, который вы получите, если выполните вышеописанные действия оптимально.

$$$^\dagger$$$ Последовательность $$$x$$$ является подпоследовательностью $$$y$$$, если $$$x$$$ может быть получена из $$$y$$$ удалением нескольких (возможно, ни одного или всех) элементов.

$$$^\ddagger$$$ Некоторыми допустимыми способами разбиения массива $$$a=[3,1,4,1,5]$$$ на $$$(s,t)$$$ являются $$$([3,4,1,5],[1])$$$, $$$([1,1],[3,4,5])$$$ и $$$([\,],[3,1,4,1,5])$$$, в то время как некоторыми недопустимыми способами разбиения $$$a$$$ являются $$$([3,4,5],[1])$$$, $$$([3,1,4,1],[1,5])$$$ и $$$([1,3,4],[5,1])$$$.

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

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

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

Вторая строка каждого набора содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$) — элементы массива $$$a$$$.

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

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

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

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

В первом наборе входных данных возможный способ разбиения $$$a$$$ — $$$s=[2,4,5]$$$ и $$$t=[1,3]$$$. Штраф равняется $$$p(s)+p(t)=2 + 1 =3$$$.

Во втором наборе входных данных возможный способ разбиения $$$a$$$ — $$$s=[8,3,1]$$$ и $$$t=[2,1,7,4,3]$$$. Штраф равняется $$$p(s)+p(t)=0 + 1 =1$$$.

В третьем наборе входных данных возможным способом разбиения $$$a$$$ является $$$s=[\,]$$$ и $$$t=[3,3,3,3,3]$$$. Штраф равняется $$$p(s)+p(t)=0 + 0 =0$$$.