题目描述

Hypercarp 正在为一艘新飞船组装控制面板。面板上有 $n$ 个信号模块排成一行。每个模块带有一种颜色的二极管，第 $i$ 个模块的颜色用整数 $a_{i}$ 表示。

测试时发现，两个相邻的同色模块可能会干扰飞行员。因此 Hypercarp 希望只保留一部分模块，使得保留下来的模块中，任意两个相邻模块颜色都不相同。

Hypercarp 可以删掉任意数量的模块。删除之后，剩余模块保持相对顺序挨在一起。除此之外，借助备用连接系统，Hypercarp 可以对剩余的模块执行最多一次交换操作：交换两个相邻的模块。不允许执行超过一次交换，也不允许在交换之后再删除模块。

求 Hypercarp 最多可以保留多少个模块，满足保留的模块中相邻颜色互不相同。

输入

本题有多组测试用例。第一行输入测试用例数量 $t$（$1 \le t \le 10^4$）。接下来给出各组测试用例的描述。

每组测试用例第一行输入一个整数 $n$（$1 \le n \le 2 \cdot 10^{5}$）——模块的初始数量。

第二行输入 $n$ 个整数 $a_{1}, a_{2}, a_{3}, ..., a_{n}$（$1 \le a_{i} \le n$）——面板上各个信号模块的颜色。

输入附加约束：

• 所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。

输出

对每组测试用例输出一个整数，表示本题答案。

样例

12
1
1
6
1 2 1 3 1 2
5
4 4 4 4 4
3
1 1 2
4
1 2 2 1
5
1 1 2 1 1
6
1 2 2 3 3 1
8
1 1 2 3 3 2 2 1
4
1 1 2 3
4
1 2 1 1
4
3 2 1 1
6
1 1 2 1 1 3

1
6
1
3
4
3
6
7
4
3
4
5

说明

第一组测试用例，面板上只有一个模块，因此可以保留它。

第二组测试用例，原本相邻模块颜色就互不相同，无需交换，可以保留全部 6 个模块。

第三组测试用例，所有模块颜色完全相同，最多只能保留一个。

第四组测试用例，可以交换第 2、3 个模块，序列由 \([1,1,2]\) 变为 \([1,2,1]\)，因此可以保留全部 3 个模块。

第五组测试用例，可以交换第 1、2 个模块，序列 \([1,2,2,1]\) 变为 \([2,1,2,1]\)，不需要删除任何模块。

第六组测试用例，可以删掉两个模块，例如保留序列 \([1,1,2]\)，交换最后两个模块得到 \([1,2,1]\)。无法保留超过 3 个模块。

第七组测试用例，可以交换第 3、4 个模块，序列 \([1,2,2,3,3,1]\) 变为 \([1,2,3,2,3,1]\)，可以保留全部 6 个模块。

第八组测试用例，可以删掉前两个颜色为 1 的模块中的一个，剩余模块序列为 \([1,2,3,3,2,2,1]\)。交换第 4、5 个模块后得到 \([1,2,3,2,3,2,1]\)，因此一共可以保留 7 个模块。

原题链接

CF2253B