A16187 | $Block Sequence$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

给定一个由 $n$ 个正整数组成的序列 $a_1, a_2, \dots, a_n$。 你可以执行任意次操作。每次操作中，你**删除**序列中的一个元素。删除元素后，剩下的元素保持原来的相对顺序。 操作结束后，剩下的序列应满足以下条件：可以将序列划分成若干个**连续的块**，使得每个块的**第一个元素的值**恰好等于该块的长度（即该块包含的元素个数）。 求最少需要删除多少个元素才能达到要求。

第一行包含一个整数 $t$（$1 \le t \le 10^4$）——测试用例的数量。 每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$）。 每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^6$）。 保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。

对于每个测试用例，输出一个整数——最少需要删除的元素个数。

输入 #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

输出 #1

C++ 编辑器

输入

输出