← 返回题目列表

Codeforces · 2146/A

A. 相同的出现次数

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

我们称数组为 平衡 当且仅当其任何元素出现的次数相同。例如,$$$[1,1,3,3,6,6]$$$ 和 $$$[2,2,2,2]$$$ 是 平衡,但 $$$[1,2,3,3]$$$ 不是 平衡 (元素$$$1$$$和$$$3$$$出现的次数不同)。请注意,空数组始终是 平衡.

给定一个由 $$$n$$$ 整数组成的非递减数组 $$$a$$$。求最长的长度 平衡 子序列$$$^{\text{*}}$$$。

$$$^{\text{*}}$$$ 序列 $$$b$$$ 是序列 $$$a$$$ 的子序列,如果 $$$b$$$ 可以通过从任意位置删除几个(可能是零个或全部)元素从 $$$a$$$ 获得。

输入

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

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 100$$$) — $$$a$$$ 的长度。

第二行包含 $$$n$$$ 整数 $$$a_1,a_2,\ldots,a_n$$$ ($$$1\le a_1\le a_2\le \cdots \le a_n\le n$$$) — $$$a$$$ 的元素。

输出

对于每个测试用例,输出一个整数 - 最长的长度 平衡 $$$a$$$ 的子序列。

示例

输入
复制

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

输出
复制

4
2
9
5

注意

在第一个测试用例中,整个数组 $$$a = [1, 1, 4, 4, 4]$$$ 不是 平衡 因为元素$$$1$$$出现的次数是$$$2$$$,而元素$$$4$$$出现的次数是$$$3$$$,它们不相等。子序列 $$$[1, 1, 4, 4]$$$ 是 平衡 因为元素$$$1$$$和$$$4$$$出现的次数都是$$$2$$$。因此,最长的长度 平衡 $$$a$$$ 的子序列是 $$$4$$$。

在第二个测试用例中,整个数组 $$$a = [1, 2]$$$ 已经 平衡,所以最长的长度 平衡 $$$a$$$ 的子序列是 $$$2$$$。

在第三个测试用例中,最长的 平衡 $$$a$$$ 的子序列是 $$$[1,1,1,2,2,2,3,3,3]$$$。

在第四个测试用例中,整个数组 $$$a = [3, 3, 3, 3, 3]$$$ 已经 平衡,所以最长的长度 平衡 $$$a$$$ 的子序列是 $$$5$$$。