CF1881E.Block Sequence

普及/提高-

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

给定一个由 $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

样例 1：删除第一个 $1$ ，剩下 $[1, 1]$ 是一个长度为 $2$ 的块，块首 $1 \neq 2$ ，但可以继续删……实际上最优是删 $1$ 个元素。
样例 2： $[2, 1, 3, 1]$ 本身就是合法的—— $[2, 1]$ 是长度 $2$ 的块（首元素 $2$ ）， $[3, 1]$ 是长度 $2$ 的块（首元素 $3$ ，但注意这里块首是 $3$ 而块长是 $2$ ——不对）。实际上需要按规则仔细验证。
核心思路： $\mathit{dp}[i]$ 表示前 $i$ 个元素中最多能保留多少个（或最少删多少个），转移时要么删掉 $a_i$ ，要么以 $a_i$ 开头形成一块。