D. Взаперти
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод
Кто тут у нас хороший массивчик? Ты хороший массивчик! (c)

Массив $$$b$$$ называется хорошим, если не существует индексов $$$1 \leq i \lt j \leq |b|$$$ таких, что $$$b_j - b_i = 1$$$.

Вам дан целочисленный массив $$$a_1, a_2, \ldots, a_n$$$. Определите минимальное количество элементов, которые нужно удалить из данного массива, чтобы он стал хорошим массивом.

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

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

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

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

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

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

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

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

В первом примере массив изначально хороший, поэтому ничего удалять не нужно.

Во втором примере оптимально удалить второй и четвёртый элементы массива — получится массив $$$1$$$, $$$3$$$, $$$5$$$.

В третьем примере массив изначально хороший.

В четвёртом примере массив изначально хороший.

В пятом примере оптимально удалить четвёртый элемент массива — получится массив $$$1$$$, $$$7$$$, $$$1$$$, $$$5$$$, $$$7$$$, $$$1$$$.

В шестом примере одно из оптимальных решений — удалить первый и четвёртый элементы массива — получится массив $$$2$$$, $$$5$$$, $$$5$$$, $$$5$$$.