解题思路

消除相邻相同物品，可以用栈模拟：

从左到右扫描序列：

• 若栈顶和当前物品相同，则二者消除，栈顶弹出；
• 否则当前物品入栈。

题目内容

茶茶同学正在玩一款一维连连看。 初始时，有一排 $n$ 个物品，从左到右编号为 $1$ 到 $n$，第 $i$ 个物品的类型为 $a_i$。

游戏过程中会不断发生消除，消除规则如下：

• 如果当前序列中存在两个相邻位置，它们的物品类型相同，那么可以选择这两个物品消除（两者都消失）；
• 消除后，剩余物品会自动靠拢，重新组成成一排；
• 当序列中不再存在相邻相同的物品时，游戏结束。

每消除一对相邻的相同的物品，记作消除 $1$ 次。

在游戏开始前，她最多可以进行一次插入操作：

• 在这排物品的任意位置插入 $1$ 个新物品（也可以选择不插入）；
• 插入位置可以在最前面、任意相邻两项之间、或最后面；
• 新物品的类型可以是任意正整数（不要求在 $[1,n]$ 内）。

请你计算：她最多可以进行多少次消除。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 $T$（$1 \le T \le 2 \times 10^5$）代表数据组数，每组测试数据描述如下：

• 第一行输入一个整数 $n$（$1 \le n \le 2 \times 10^5$），表示物品数。
• 第二行输入 $n$ 个整数 $a_1,a_2,\dots,a_n$（$1 \le a_i \le n$），表示每个物品的类型。

除此之外，保证单个测试文件的 $n$ 之和不超过 $4 \times 10^5$。

输出描述

对于每一组测试数据，新起一行，输出茶茶同学最多可以消除多少次。

样例1

输入

2
4
1 2 2 1
5
1 1 2 3 3

输出

2
3

说明

第 $1$ 组数据：初始序列为 $(1,2,2,1)$。

• 相邻的 $(2,2)$ 消除后，序列变为 $(1,1)$；
• 相邻的 $(1,1)$ 再消除，序列变为空；
• 总共消除 $2$ 次，即使插入新物品，也无法让消除次数超过 $2$，因此答案为 $2$。