## GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

# [Solution] Doremy's Paint Codeforces Solution

A. Doremy's Paint
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

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\left(l,r\right)$ be the number of distinct elements in the subarray $\left[{a}_{l},{a}_{l+1},\dots ,{a}_{r}\right]$. Choose $2$ integers $l$ and $r$ such that $l\le r$ and $r-l-c\left(l,r\right)$ is maximized.

Input

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},\dots ,{a}_{n}$ ($1\le {a}_{i}\le n$).

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

Output

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

If there are multiple solutions, you may output any.

Note

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

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

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

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

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

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