F2. Летающая сортировка (сложная версия)
ограничение по времени на тест
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, 2, 9]$$$, то можно применить следующую последовательность операций:

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

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

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

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

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

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

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

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

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

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

Пример
Входные данные
9
5
4 7 2 2 9
5
3 5 8 1 7
5
1 2 2 4 5
2
0 1
3
0 1 0
4
0 1 0 0
4
0 1 0 1
4
0 1 0 2
20
16 15 1 10 0 14 0 10 3 9 2 5 4 5 17 9 10 20 0 9
Выходные данные
2
2
0
0
1
1
1
1
16
Примечание

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

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

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