题目内容

给定一个长度为 $n$ 的正整数序列 $a_1, a_2, \dots, a_n$。你可以反复执行如下操作：如果存在两个相邻且值相等的元素，则将它们删除，删除后左右两侧剩余序列会自动拼接。每删除一对元素计为 $1$ 次删除。

在所有操作开始之前，你拥有一次机会，可以在序列的任意位置（包括最前、最后或任意两个元素之间）插入一个任意的正整数；你也可以选择不插入。

请你计算，通过最优的插入和后续操作，最多能进行多少次删除。

约束条件

• 测试数据组数 $T$ 满足 $1 \le T \le 2 \times 10^5$。
• 对于每组数据，序列长度 $n$ 满足 $1 \le n \le 2 \times 10^5$。
• 序列中的每个整数 $a_i$ 满足 $1 \le a_i \le n$。
• 所有组别的 $n$ 之和不超过 $4 \times 10^5$。

输入描述

输入包含多组测试数据。第一行一个整数 $T$，表示数据组数。接下来依次描述每组数据，每组数据包含两行：第一行一个整数 $n$，表示序列长度；第二行 $n$ 个整数，表示序列元素。

输出描述

对于每组数据，输出一行一个整数，表示最多能执行的删除次数。

样例1

输入

1
1
5

输出

1

说明

序列长度 $n=1$，元素为 5。使用栈模拟消除后得到 $b=[5]$，长度 $m=1$。基础消除次数 $base=\frac{n-m}{2}=0$。由于 $m>0$，在 $b$ 中求最长奇回文半径。对于单个元素 5，以它为中心的回文半径为 1，因此额外消除次数 $extra=1$。最终答案为 $0+1=1$。实际操作：在 5 的旁边插入一个 5 形成 [5,5]，即可消除一对，获得 1 次删除。

样例2

输入

1
4
1 2 2 1

输出

2

说明

$n=4$，序列 [1,2,2,1]。模拟消除：1 入栈，2 入栈，遇到 2 与栈顶相同弹出，栈为 [1]；遇到 1 与栈顶相同弹出，栈空。简化序列为空，$m=0$。基础消除次数 $base=\frac{4-0}{2}=2$。由于 $m=0$，无法通过插入获得新消除，$extra=0$。最终答案为 2。序列本身就可以完全消除，无需插入。

样例3

输入

1
7
1 3 3 2 1 2 1

输出

4

说明

$n=7$，序列 [1,3,3,2,1,2,1]。栈模拟：1, 3 入栈；第二个 3 与栈顶 3 消除，栈变为 [1]；2 入栈变为 [1,2]；1 入栈变为 [1,2,1]；2 与栈顶 1 不同，入栈变为 [1,2,1,2]；1 入栈变为 [1,2,1,2,1]。简化序列 $b=[1,2,1,2,1]$，长度 $m=5$。基础消除次数 $base=\frac{7-5}{2}=1$。对 $b$ 求最长奇回文半径：以中间的 1（第 3 个元素，下标 2）为中心，向两边扩展可得到 $b[1]=2$ 与 $b[3]=2$ 相等，$b[0]=1$ 与 $b[4]=1$ 相等，回文半径 $k=3$，故 $extra=3$。总删除次数 $1+3=4$。实际操作：可在中间 1 旁插入一个 1，先后消除 1,1、2,2、1,1，加上原来消除的 3,3，共 4 次删除。