← 返回题目列表

Codeforces · 1625/B

B. 基本粒子

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

火星人积极从事星际贸易。奥林普城,这座以太空港闻名的火星城市,已经成为来自银河各个角落的货物的聚集地。为了从遥远的行星运送更多的货物,火星人需要快速的宇宙飞船。

一组科学家进行实验,为新型宇宙飞船建造快速发动机。在当前的实验中,有 $$$n$$$ 个基本粒子,其中第 $$$i$$$ 的类型为 $$$a_i$$$。

将粒子序列 ($$$a_1, a_2, \dots, a_n$$$) 的子段表示为某些左边界 $$$l$$$ 和右边界 $$$r$$$ 的序列 ($$$a_l, a_{l+1}, \dots, a_r$$$) ($$$1 \le l \le r \le n$$$)。例如,$$$l=2$$$ 和 $$$r=4$$$ 的序列 $$$(1\ 4\ 2\ 8\ 5\ 7)$$$ 具有序列 $$$(4\ 2\ 8)$$$ 作为子段。如果两个子段的至少一个边界不同,则认为这些子段是不同的。

请注意,子段可以与序列相同,但仍被视为不同。例如,考虑序列 $$$(1\ 1\ 1\ 1\ 1)$$$ 及其两个子段:一个具有 $$$l=1$$$ 和 $$$r=3$$$,另一个具有 $$$l=2$$$ 和 $$$r=4$$$。两个子段都等于 $$$(1\ 1\ 1)$$$,但仍被视为不同,因为它们的左边界和右边界不同。

科学家们想要进行反应以获得两个相同长度的不同子片段。表示这个长度$$$k$$$。由此产生的一对子段必须是和谐的,即。 e.对于某些$$$i$$$ ($$$1 \le i \le k$$$),这两个子段的第$$$i$$$位置上的粒子类型一定是相同的。例如,$$$(1\ 7\ 3)$$$ 和 $$$(4\ 7\ 8)$$$ 是和谐的,因为两个子段在第二个位置上都有 $$$7$$$。 $$$(1\ 2\ 3)$$$ 和 $$$(3\ 1\ 2)$$$ 并不和谐。

和谐的子段越长,科学家们设计快速发动机的机会就越大。因此,他们要求你计算由不同子段组成的和谐对的最大可能长度。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 100$$$) — 测试用例的数量。以下是测试用例的描述。

第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 150\,000$$$) — 序列中基本粒子的数量。

第二行包含 $$$n$$$ 整数 $$$a_i$$$ ($$$1 \le a_i \le 150\,000$$$) — 基本粒子的类型。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$3\cdot10^5$$$。

输出

对于每个测试,打印一个整数,即由不同子段组成的和谐对的最大可能长度。如果这样的对不存在,则打印$$$-1$$$。

示例

输入 #1

4
7
3 1 5 2 1 3 4
6
1 1 1 1 1 1
6
1 4 2 8 5 7
2
15 15

输出 #1

4
5
-1
1

注意

第一个测试用例如下图所示:

从中可以看出,您可以选择子段$$$(2\ 1\ 3\ 4)$$$和$$$(3\ 1\ 5\ 2)$$$,它们是和谐的一对。它们的长度等于$$$4$$$,所以答案是$$$4$$$。

在第二个测试用例中,您需要采用两个子段:一个包含 $$$l=1$$$ 和 $$$r=5$$$,另一个包含 $$$l=2$$$ 和 $$$r=6$$$。不难看出,这些段是和谐的一对,并且被认为是不同的,即使它们都等于 $$$(1\ 1\ 1\ 1\ 1)$$$。

在第三个测试用例中,你无法组成和谐的一对,所以答案是$$$-1$$$。