← 返回题目列表

Codeforces · 1761/B

B. 消除环

中文机器翻译题面 查看原题

将大小为$$$n$$$的循环序列定义为长度为$$$n$$$的数组$$$s$$$,其中$$$s_n$$$与$$$s_1$$$相邻。

Muxii 有一个由大小为 $$$n$$$ 的循环序列 $$$a$$$ 表示的环。

然而,环本身讨厌相等的相邻元素。因此,如果序列中的两个相邻元素在任何时候相等,则其中一个将立即被删除。该序列最初不包含相等的相邻元素。

Muxii 可以执行以下操作,直到序列变空:

- 选择 $$$a$$$ 中的一个元素并将其删除。

例如,如果ring是$$$[1, 2, 4, 2, 3, 2]$$$,并且Muxii擦除元素$$$4$$$,那么ring将擦除等于$$$2$$$的元素之一,并且ring将变成$$$[1, 2, 3, 2]$$$。

Muxii 想要找到他可以执行的最大操作数。

请注意,在 $$$1$$$ 大小的环中,其唯一元素不被视为与其自身相邻(因此不会立即删除)。

输入

每个测试包含多个测试用例。第一行包含一个整数 $$$t$$$ ($$$1\leq t\leq 100$$$)——测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1\leq n\leq 100$$$) — 循环序列的大小。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1,a_2,\ldots,a_n$$$ ($$$1\leq a_i\leq n$$$) - 序列本身。

保证 $$$a_i\ne a_{i+1}$$$ 对于 $$$1\leq i<n$$$。

当$$$n>1$$$时,保证$$$a_n\ne a_1$$$。

输出

对于每个测试用例,输出一个整数 - Muxii 可以执行的最大操作数。

示例

输入 #1

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

输出 #1

4
3
1

注意

在第一个测试用例中,您可以先擦除第二个元素,然后以任意顺序逐个擦除剩余元素。总共,您可以执行操作 $$$4$$$ 次。请注意,如果先删除第一个元素,则序列将变成 $$$[2,3,2]$$$,然后立即变成 $$$[2,3]$$$。

在第二个测试用例中,可以先擦除第一个元素,然后序列变为$$$[2,1]$$$。然后您可以按任意顺序一一删除所有剩余元素。