CF1764A.Doremy's Paint

Doremy has $n$ buckets of paint which is represented by an array $a$ of length $n$. Bucket $i$ contains paint with color $a_i$.

Let $c(l,r)$ be the number of distinct elements in the subarray $[a_l,a_{l+1},\ldots,a_r]$. Choose $2$ integers $l$ and $r$ such that $l \leq r$ and $r-l-c(l,r)$ is maximized.

Doremy 有 $n$ 桶颜料，用一个长度为 $n$ 的数组 $a$ 表示。第 $i$ 桶颜料的颜色为 $a_i$。

令 $c(l,r)$ 表示子数组 $[a_l,a_{l+1},\ldots,a_r]$ 中不同元素的个数。请选择两个整数 $l$ 和 $r$，满足 $l \leq r$，使得 $r-l-c(l,r)$ 最大化。

The input consists of multiple test cases. The first line contains a single integer $t$ ($1\le t\le 10^4$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1 \le n \le 10^5$) — the length of the array $a$.

The second line of each test case contains $n$ integers $a_1,a_2,\ldots,a_n$ ($1 \le a_i \le n$).

It is guaranteed that the sum of $n$ does not exceed $10^5$.

输入包含多个测试用例。第一行包含一个整数 $t$（$1\le t\le 10^4$），表示测试用例的数量。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 10^5$），表示数组 $a$ 的长度。

每个测试用例的第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$（$1 \le a_i \le n$）。

保证所有测试用例的 $n$ 之和不超过 $10^5$。

For each test case, output $l$ and $r$ such that $l \leq r$ and $r-l-c(l,r)$ is maximized.

If there are multiple solutions, you may output any.

对于每个测试用例，输出满足 $l \leq r$ 且使 $r-l-c(l,r)$ 最大的 $l$ 和 $r$。

若存在多个解，可输出任意一个。

In the first test case, $a=[1,3,2,2,4]$.

• When $l=1$ and $r=3$, $c(l,r)=3$ (there are $3$ distinct elements in $[1,3,2]$).
• When $l=2$ and $r=4$, $c(l,r)=2$ (there are $2$ distinct elements in $[3,2,2]$).

It can be shown that choosing $l=2$ and $r=4$ maximizes the value of $r-l-c(l,r)$ at $0$.

For the second test case, $a=[1,2,3,4,5]$.

• When $l=1$ and $r=5$, $c(l,r)=5$ (there are $5$ distinct elements in $[1,2,3,4,5]$).
• When $l=3$ and $r=3$, $c(l,r)=1$ (there is $1$ distinct element in $[3]$).

It can be shown that choosing $l=1$ and $r=5$ maximizes the value of $r-l-c(l,r)$ at $-1$. Choosing $l=3$ and $r=3$ is also acceptable.

在第一个测试用例中，$a=[1,3,2,2,4]$。

• 当 $l=1$ 且 $r=3$ 时，$c(l,r)=3$（子数组 $[1,3,2]$ 中有 $3$ 个互不相同的元素）。
• 当 $l=2$ 且 $r=4$ 时，$c(l,r)=2$（子数组 $[3,2,2]$ 中有 $2$ 个互不相同的元素）。

可以证明：选择 $l=2$ 和 $r=4$ 可使 $r-l-c(l,r)$ 的值最大化，最大值为 $0$。

在第二个测试用例中，$a=[1,2,3,4,5]$。

• 当 $l=1$ 且 $r=5$ 时，$c(l,r)=5$（子数组 $[1,2,3,4,5]$ 中有 $5$ 个互不相同的元素）。
• 当 $l=3$ 且 $r=3$ 时，$c(l,r)=1$（子数组 $[3]$ 中有 $1$ 个互不相同的元素）。

可以证明：选择 $l=1$ 和 $r=5$ 可使 $r-l-c(l,r)$ 的值最大化，最大值为 $-1$。选择 $l=3$ 和 $r=3$ 同样可接受。