Олимпиадный тренинг

Задача . E. Блоковая последовательность


Задача

Темы: дп *1500

Дана последовательность целых чисел \(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\) стала красивой.

Примечание

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

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

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


Примеры
Входные данныеВыходные данные
1 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

time 2000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w643
Комментарий учителя