E. Блоковая последовательность
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дана последовательность целых чисел $$$a$$$ длины $$$n$$$.

Назовём последовательность красивой, если она имеет вид ряда блоков, каждый из которых начинается со своей длины, то есть сначала идёт длина блока, а потом его элементы. Например, последовательности [$$$\color{red}{3},\ \color{red}{3},\ \color{red}{4},\ \color{red}{5},\ \color{green}{2},\ \color{green}{6},\ \color{green}{1}$$$] и [$$$\color{red}{1},\ \color{red}{8},\ \color{green}{4},\ \color{green}{5},\ \color{green}{2},\ \color{green}{6},\ \color{green}{1}$$$] являются красивыми (разные блоки покрашены разными цветами), а [$$$1$$$], [$$$1,\ 4,\ 3$$$], [$$$3,\ 2,\ 1$$$] — нет.

За одну операцию вы можете удалить из последовательности любой элемент. Какое минимальное количество операций нужно сделать, чтобы данная последовательность стала красивой.

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

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

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

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

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

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

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

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

В первом наборе входных данных примера данная последовательность уже является красивой, как и показано в условии.

Во втором наборе входных данных примера можно сделать последовательность красивой только удалив из неё все элементы.

В пятом наборе входных данных примера можно сделать последовательность красивой, удалив первый и последний элемент. Тогда последовательность станет [$$$2,\ 3,\ 4$$$].