Codeforces Round 903 (Div. 3) |
---|
Закончено |
Дана последовательность целых чисел $$$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$$$ стала красивой.
773 3 4 5 2 6 145 6 3 263 4 1 6 7 731 4 351 2 3 4 551 2 3 1 254 5 5 1 5
0 4 1 1 2 1 0
В первом наборе входных данных примера данная последовательность уже является красивой, как и показано в условии.
Во втором наборе входных данных примера можно сделать последовательность красивой только удалив из неё все элементы.
В пятом наборе входных данных примера можно сделать последовательность красивой, удалив первый и последний элемент. Тогда последовательность станет [$$$2,\ 3,\ 4$$$].
Название |
---|