CF1625B.Elementary Particles

Martians are actively engaged in interplanetary trade. Olymp City, the Martian city known for its spaceport, has become a place where goods from all the corners of our Galaxy come. To deliver even more freight from faraway planets, Martians need fast spaceships.

A group of scientists conducts experiments to build a fast engine for the new spaceship. In the current experiment, there are $n$ elementary particles, the $i$-th of them has type $a_i$.

Denote a subsegment of the particle sequence ($a_1, a_2, \dots, a_n$) as a sequence ($a_l, a_{l+1}, \dots, a_r$) for some left bound $l$ and right bound $r$ ($1 \le l \le r \le n$). For instance, the sequence $(1\ 4\ 2\ 8\ 5\ 7)$ for $l=2$ and $r=4$ has the sequence $(4\ 2\ 8)$ as a subsegment. Two subsegments are considered different if at least one bound of those subsegments differs.

Note that the subsegments can be equal as sequences but still considered different. For example, consider the sequence $(1\ 1\ 1\ 1\ 1)$ and two of its subsegments: one with $l=1$ and $r=3$ and another with $l=2$ and $r=4$. Both subsegments are equal to $(1\ 1\ 1)$, but still considered different, as their left and right bounds differ.

The scientists want to conduct a reaction to get two different subsegments of the same length. Denote this length $k$. The resulting pair of subsegments must be harmonious, i. e. for some $i$ ($1 \le i \le k$) it must be true that the types of particles on the $i$-th position are the same for these two subsegments. For example, the pair $(1\ 7\ 3)$ and $(4\ 7\ 8)$ is harmonious, as both subsegments have $7$ on the second position. The pair $(1\ 2\ 3)$ and $(3\ 1\ 2)$ is not harmonious.

The longer are harmonious subsegments, the more chances for the scientists to design a fast engine. So, they asked you to calculate the maximal possible length of harmonious pair made of different subsegments.

火星人正积极从事星际贸易。以航天港闻名的火星城市奥林匹亚城，已成为银河系各个角落货物汇聚之地。为了从遥远的星球运送更多货物，火星人需要更快的宇宙飞船。

一组科学家正在进行实验，旨在为新型宇宙飞船研制一种高速引擎。在当前的实验中，有 $n$ 个基本粒子，其中第 $i$ 个粒子的类型为 $a_i$。

将粒子序列 $(a_1, a_2, \dots, a_n)$ 的一个子段（subsegment）定义为形如 $(a_l, a_{l+1}, \dots, a_r)$ 的序列，其中 $l$ 和 $r$ 分别为左端点与右端点，且满足 $1 \le l \le r \le n$。例如，对序列 $(1\ 4\ 2\ 8\ 5\ 7)$，当 $l=2$、$r=4$ 时，其对应子段为 $(4\ 2\ 8)$。若两个子段的至少一个端点不同，则认为它们是不同的子段。

注意：即使两个子段作为序列完全相同，只要其端点不同，仍视为不同的子段。例如，考虑序列 $(1\ 1\ 1\ 1\ 1)$ 及其两个子段：一个对应 $l=1$、$r=3$，另一个对应 $l=2$、$r=4$。这两个子段均为 $(1\ 1\ 1)$，但由于端点不同，仍被视为不同的子段。

科学家希望引发一次反应，从而得到两个长度相同且互不相同的子段。记该公共长度为 $k$。所得的这一对子段必须是和谐的（harmonious），即：存在某个位置 $i$（$1 \le i \le k$），使得这两个子段在第 $i$ 个位置上的粒子类型相同。例如，子段对 $(1\ 7\ 3)$ 与 $(4\ 7\ 8)$ 是和谐的，因为二者在第二个位置上均为 $7$；而子段对 $(1\ 2\ 3)$ 与 $(3\ 1\ 2)$ 则不和谐。

和谐子段对的长度越长，科学家设计出高速引擎的可能性就越大。因此，他们请你计算：由两个互不相同的子段构成的和谐子段对的最大可能长度。

The first line contains an integer $t$ ($1 \le t \le 100$) — the number of test cases. The following are descriptions of the test cases.

The first line contains an integer $n$ ($2 \le n \le 150\,000$) — the amount of elementary particles in the sequence.

The second line contains $n$ integers $a_i$ ($1 \le a_i \le 150\,000$) — types of elementary particles.

It is guaranteed that the sum of $n$ over all test cases does not exceed $3\cdot10^5$.

第一行包含一个整数 $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$。

For each test, print a single integer, maximal possible length of harmonious pair made of different subsegments. If such pair does not exist, print $-1$ instead.

对于每组测试，输出一个整数，表示由不同子段构成的和谐对的最大可能长度。如果不存在这样的对，则输出 $-1$。

The first test case is shown on the picture below:

As you can see from it, you may choose the subsegments $(2\ 1\ 3\ 4)$ and $(3\ 1\ 5\ 2)$, which are a harmonious pair. Their length is equal to $4$, so the answer is $4$.

In the second test case, you need to take two subsegments: one with $l=1$ and $r=5$, and one with $l=2$ and $r=6$. It's not hard to observe that these segments are a harmonious pair and considered different even though they are both equal to $(1\ 1\ 1\ 1\ 1)$.

In the third test case, you cannot make a harmonious pair, so the answer is $-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$。