CF1987F2.Interesting Problem (Hard Version)

这是该问题的困难版本。两种版本的唯一区别在于 $n$ 的限制。只有当你同时解决了两个版本的问题时，才能进行 Hack。

给定一个长度为 $n$ 的整数数组 $a$。

每次操作，你需要执行以下两步：

1. 选择一个下标 $i$，满足 $1 \le i < |a|$ 且 $a_i = i$。
2. 从数组中移除 $a_i$ 和 $a_{i+1}$，并将剩余部分拼接起来。

请你求出最多可以执行上述操作多少次。

每组测试数据包含多个测试用例。输入的第一行包含一个整数 $t$（$1 \le t \le 100$），表示测试用例的数量。接下来的每组测试用例描述如下：

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 800$），表示数组 $a$ 的长度。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le n$），表示数组 $a$ 的元素。

保证所有测试用例中 $n$ 的总和不超过 $800$。

对于每个测试用例，输出一个整数，表示最多可以执行操作的次数。

在第一个测试用例中，一种可能的最优操作序列为 $[1, 5, \color{red}{3}, \color{red}{2}, 4] \rightarrow [\color{red}{1}, \color{red}{5}, 4] \rightarrow [4]$。

在第三个测试用例中，一种可能的最优操作序列为 $[1, \color{red}{2}, \color{red}{3}] \rightarrow [1]$。

由 ChatGPT 4.1 翻译