[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(l,r)$ be the number of distinct elements in the subarray [𝑎𝑙,𝑎𝑙+1,…,𝑎𝑟]$[a_l,a_{l+1},\dots ,a_r]$. Choose 2$2$ integers 𝑙$l$ and 𝑟$r$ such that 𝑙≤𝑟$l\le r$ and 𝑟−𝑙−𝑐(𝑙,𝑟)$r-l-c(l,r)$ is maximized.

Input

The input consists of multiple test cases. The first line contains a single integer 𝑡$t$ (1≤𝑡≤104$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≤𝑛≤105$1\le n\le {10}^5$) — the length of the array 𝑎$a$.

The second line of each test case contains 𝑛$n$ integers 𝑎1,𝑎2,…,𝑎𝑛$a_1,a_2,\dots ,a_n$ (1≤𝑎𝑖≤𝑛$1\le a_i\le n$).

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

Output

For each test case, output 𝑙$l$ and 𝑟$r$ such that 𝑙≤𝑟$l\le r$ and 𝑟−𝑙−𝑐(𝑙,𝑟)$r-l-c(l,r)$ is maximized.

If there are multiple solutions, you may output any.

Note

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

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

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

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

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

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