CF 1764A - 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 ai.

Let c(l,r) be the number of distinct elements in the subarray [al,al+1,…,ar].

 Choose 2 integers l and r such that l≤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≤t≤104)  — 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≤n≤105) — the length of the array a.

The second line of each test case contains n integers a1,a2,…,an (1≤ai≤n).

It is guaranteed that the sum of n does not exceed 105.

Output

For each test case, output l and r such that l≤r and r−l−c(l,r) is maximized.

If there are multiple solutions, you may output any.

Example

input

7

5

1 3 2 2 4

5

1 2 3 4 5

4

2 1 2 1

3

2 3 3

2

2 2

1

1

9

9 8 5 2 1 1 2 3 3

output

2 4

1 5

1 4

2 3

1 2

1 1

3 9

Note

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

---------------------------------

理解题意就好了，其实对于左边的数字没有影响的，就是如何找到右边的数字，这里面右边的数字必须是有重复值的最右边的这个数字。找到即可返回。

代码如下：