C. 将数字排成圆圈 / Arrange the Numbers in a Circle

题目描述

你有若干张卡片：$c_1$ 张数字 $1$ 的卡片，$c_2$ 张数字 $2$ 的卡片，……，$c_n$ 张数字 $n$ 的卡片。

你必须从中选出 至少三张 卡片，排成一个圆圈，使得满足以下条件：

• 每连续三张卡片中，至少有两张 数字相同。

设圆圈中卡片的数字依次为 $a_0, a_1, \dots, a_{k-1}$，则条件为：

• 对于每个 $i$ 从 $0$ 到 $k-1$，$a_i, a_{(i+1) \bmod k}, a_{(i+2) \bmod k}$ 中至少有两个相等。

问最多能排出多少张卡片？

输入格式

第一行包含一个整数 $t$ ($1 \le t \le 10^4$) — 测试用例数量。

每个测试用例包含两行：

• 第一行包含一个整数 $n$ ($1 \le n \le 2 \cdot 10^5$)；
• 第二行包含 $n$ 个整数 $c_1, c_2, \dots, c_n$ ($1 \le c_1 \le c_2 \le \dots \le c_n \le 10^9$)。

额外限制：所有测试用例中 $n$ 之和不超过 $2 \cdot 10^5$。

输出格式

对于每个测试用例，输出一个整数 — 能排出的最大卡片数。如果无法选出至少三张卡片排成合法圆圈，输出 $0$。

样例

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

4
9
3

提示

第一个例子中，可以选出并排列卡片为 $[4, 2, 4, 4]$。无法排出超过 $4$ 张。例如 $[2, 4, 4, 1, 4]$ 不合法，因为圆圈中倒数第二、最后和第一张构成的三元组也不满足条件。

第二个例子中，可以排出全部卡片：$[1, 1, 2, 2, 2, 3, 3, 3, 3]$。

第三个例子中，可以选出并排列卡片为 $[5, 5, 6, 6, 3, 6, 6, 5]$。