CF1699D Almost Triple Deletions

给定一个整数 $n$ 和一个数组 $a_1,a_2,\ldots,a_n$。 每次操作，你可以选择一个下标 $i$（$1 \le i < n$），满足 $a_i \neq a_{i+1}$，并将 $a_i$ 和 $a_{i+1}$ 同时从数组中删除。删除后，数组的剩余部分会自动拼接在一起。 例如，如果 $a=[1,4,3,3,6,2]$，那么对 $i=2$ 执行一次操作后，得到的新数组为 $[1,3,6,2]$。 通过若干次（也可以不进行）上述操作，能从 $a$ 得到的所有元素都相等的数组的最大可能长度是多少？

每个测试点包含多个测试用例。输入的第一行包含一个整数 $t$（$1 \le t \le 1000$），表示测试用例的数量。接下来的每组测试用例描述如下。 每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 5000$），表示数组 $a$ 的长度。 第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$（$1 \le a_i \le n$），表示数组 $a$ 的元素。 保证所有测试用例中 $n$ 的总和不超过 $10\,000$。

对于每个测试用例，输出一个整数，表示通过若干次操作后，能得到的所有元素都相等的数组的最大可能长度。

对于第一个测试用例，一种最优的操作序列为：$[1,2,3,2,1,3,3] \rightarrow [3,2,1,3,3] \rightarrow [3,3,3]$。 对于第二个测试用例，数组中的所有元素已经相等。 对于第三个测试用例，唯一可能的操作序列为：$[1,1,1,2,2,2] \rightarrow [1,1,2,2] \rightarrow [1,2] \rightarrow []$。注意，每次删除的元素必须不同。 对于第四个测试用例，最优的操作序列为：$[1,1,2,2,3,3,1,1] \rightarrow [1,1,2,3,1,1] \rightarrow [1,1,1,1]$。 对于第五个测试用例，可以得到的所有元素都相等的数组之一为 $[4,4]$。 由 ChatGPT 4.1 翻译