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.


-----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,\ldots,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 \leq r$ and $r-l-c(l,r)$ is maximized.

If there are multiple solutions, you may output any.


-----Examples-----

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 acceptable.

Difficulty: EASY
Tags: Greedy algorithms
Skill types: Greedy algorithms

Starter code:

Solutions:
import sys
inputs = ''.join(sys.stdin.readlines()).strip().split('\n')[2::2]
for i in inputs:
	if len(i.split()) > 1:
		print(1, len(i.split()))
	else:
		print(1, 1)


import sys

def solve():
	input = sys.stdin.readline
	n = int(input())
	input()
	print(f'{1} {n}')

def main():
	t = int(input())
	for _ in range(t):
		solve()
main()


import sys
s = sys.stdin.read()
lines = s.split('\n')
for index in range(1, len(lines) - 2, 2):
	lenght = int(lines[index])
	data = lines[index + 1]
	print(1, lenght)


for s in [*open(0)][2::2]:
	print(1, len(s.split()))


import sys
from collections import deque
n = int(sys.stdin.readline().strip())
for i in range(n):
	m = int(sys.stdin.readline().strip())
	o = sys.stdin.readline()
	print(1, m)


for i in [*open(0)][2::2]:
	print(1, end=' ')
	print(len(i.split()))


for i in [*open(0)][1::2]:
	print(1, i, end='')


import sys
input = sys.stdin.readline

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())
test_cases = inp()
inp_arr = []
for i in range(test_cases):
	num = inp()
	nums = inlt()
	inp_arr.append(nums)

def findResult(nums):
	return f'1 {len(nums)}'
result = [findResult(cheeses) for cheeses in inp_arr]
for m in result:
	print(m)


ans = []
for _ in range(int(input())):
	n = int(input())
	s = input()
	ans.append([1, n])
for i in ans:
	print(*i)


import sys
input = iter(sys.stdin.read().splitlines()).__next__
TC = int(input())
for tc in range(TC):
	N = int(input())
	A = list(map(int, input().split()))
	print(1, N)


import sys

def solve():
	inp = sys.stdin.readline
	n = int(inp())
	inp()
	print(1, n)

def main():
	for i in range(int(sys.stdin.readline())):
		solve()
main()


import sys
import math
FILE = False
if FILE:
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')

def get_int():
	return int(sys.stdin.readline())

def get_string():
	return sys.stdin.readline().strip()

def write_int(n):
	return sys.stdout.write(str(n) + '\n')

def write_list(list):
	sys.stdout.write(' '.join(map(str, list)) + '\n')

def compute_cost(x, y):
	if x == 0:
		return y * y
	if y == 0:
		return x * x
	return x * y
test_cases = get_int()
for test in range(test_cases):
	n = get_int()
	input = [int(x) for x in get_string().split()]
	print(1, n)


def main():
	t = int(input())
	result = []
	for i in range(t):
		n = int(input())
		arr = [int(x) for x in input().split()]
		result.append('1 ' + str(n))
	print(*result, sep='\n')
main()


import sys
inp = sys.stdin.readline
input = lambda : inp().strip()
ii = lambda : int(input())
mi = lambda : map(int, input().split())
li = lambda : list(map(int, input().split()))
for _ in range(ii()):
	n = ii()
	nums = li()
	print(1, n)


import os.path
from math import gcd, floor, ceil
from collections import *
import sys
mod = 1000000007
INF = float('inf')

def st():
	return list(sys.stdin.readline().strip())

def li():
	return list(map(int, sys.stdin.readline().split()))

def mp():
	return map(int, sys.stdin.readline().split())

def inp():
	return int(sys.stdin.readline())

def pr(n):
	return sys.stdout.write(str(n) + '\n')

def prl(n):
	return sys.stdout.write(str(n) + ' ')
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
t = inp()
for i in range(t):
	n = inp()
	l = li()
	print(1, n)


t = int(input())
o = []
for i in range(t):
	n = int(input())
	a = input().split()
	a2 = set(a)
	L = 0
	R = n - 1
	if len(a2) == len(a):
		o.append((L + 1, R + 1))
	else:
		for j in range(n):
			if a[j] in a2:
				L = j
				break
		for j in range(n - 1, -1, -1):
			if a[j] in a2:
				R = j
				break
		o.append((L + 1, R + 1))
for e in o:
	print(e[0], e[1])


def solve():
	n = input()
	a = input()
	print('1 ' + n)
t = int(input())
for _ in range(t):
	solve()


import sys
from bisect import bisect_left, bisect_right
from heapq import heapify, heappush, heappop
from collections import deque
from math import gcd, sqrt, log10, log2, floor, ceil, sqrt
from collections import deque, defaultdict
input = sys.stdin.readline

def il():
	return [int(a) for a in input().strip().split()]

def ip():
	return input().strip()

def ii():
	return int(input())
mod = 1000000000 + 7
dx = [-1, -2, 1, 2, 2, -2, -1, 1]
dy = [2, 1, 2, 1, -1, -1, -2, -2]
for _ in range(ii()):
	n = ii()
	arr = il()
	print(1, n)


t = int(input())
s = []
for i in range(t):
	n = int(input())
	p = -n
	k = list(map(int, input().split()))
	if len(k) - 1 - len(set(k)) < -1:
		s.append('1 1')
	else:
		s.append('1 ' + str(len(k)))
for h in s:
	print(h)


t = int(input())
for i in range(t):
	print(f'1 {input()}')
	input()


import sys
from collections import *
sys.setrecursionlimit(10 ** 5)
itr = (line for line in sys.stdin.read().strip().split('\n'))
INP = lambda : next(itr)

def ni():
	return int(INP())

def nl():
	return [int(_) for _ in INP().split()]

def solve(n, a):
	print(1, n)
t = ni()
for case in range(t):
	n = ni()
	a = nl()
	solve(n, a)


t = input()
for i in range(0, int(t)):
	n = input()
	a = input().split(' ')
	print('1 ' + n)


def ans(n, a):
	return [1, n]
T = int(input())
r = []
for i in range(T):
	n = int(input())
	a = list(map(int, input().split()))
	c = ans(n, a)
	r.append(c)
for i in range(T):
	print(' '.join(map(str, r[i])))


t = int(input())
for coasdjf in range(t):
	n = int(input())
	s = input()
	print(f'1 {n}')


t = int(input())
for i in range(t):
	n = int(input())
	a = input()
	print(1, n)


for _ in range(int(input())):
	n = int(input())
	input()
	print(f'1 {n}')


for _ in range(int(input())):
	N = int(input())
	input()
	print('1', N)


def sol():
	n = int(input())
	for i in range(n):
		le = int(input())
		l = map(int, input().split(' '))
		print(1, le)
sol()


n = int(input())
for i in range(n):
	a = int(input())
	b = input()
	print(1, a)


for _ in range(int(input())):
	x = int(input())
	input()
	print(1, x)


n = input()
for d in range(int(n)):
	input()
	a = input().split()
	print('1 ' + str(len(a)))


T = int(input())
for _ in range(T):
	n = int(input())
	_ = input()
	print(1, n)


n = int(input())
for i in range(n):
	x = int(input())
	l = input().split(' ')
	print(1, len(l))


for i in range(int(input())):
	n = int(input())
	dp = input()
	print(1, n)


for s in range(int(input())):
	bucket = input()
	paint = input()
	print('1', bucket)


for i in range(int(input())):
	print(1, int(input()))
	input()


t = int(input())
for i in range(0, t):
	n = int(input())
	l1 = input()
	print('1', n)


t = int(input())
for _ in range(t):
	(n, a) = (int(input()), (int(i) for i in input().split()))
	res = (1, n)
	print(*res)


for _ in range(int(input())):
	n = int(input())
	arr = input().split()
	print(1, n)


n = int(input())
for i in range(n):
	x = int(input())
	y = input()
	print(1, x)


for i in range(int(input())):
	n = int(input())
	list1 = input().split()
	print(1, n)


x = int(input())
for i in range(x):
	p = int(input())
	data = input()
	data_lst = data.split(' ')
	print(1, len(data_lst))


for _ in range(int(input())):
	n = int(input())
	b = list(map(int, input().split()))
	print(1, n)


for _ in range(int(input())):
	n = int(input())
	l = input()
	print(1, n)


for i in range(int(input())):
	a = int(input())
	b = input().split()
	print(1, ' ', a)


for t in range(0, int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	print(1, n)


T = int(input())
for tc in range(T):
	n = int(input())
	l1 = list(map(int, input().split()))
	print(1, n)


t = int(input())
for _ in range(t):
	n = int(input())
	a = map(int, input().split())
	print(1, n)


T = int(input())
for h in range(T):
	n = int(input())
	a = list(map(int, input().split()))
	print(f'1 {n}')


x = int(input())
while x:
	x -= 1
	y = int(input())
	z = input()
	print(1, y, sep=' ')


def sol():
	n = int(input())
	a = map(int, input().split())
	print(1, n)
for i in range(int(input())):
	sol()


for run in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	print(1, n)


t = int(input())
for i in range(t):
	n = int(input())
	arr = input().split()
	print(1, n)


t = int(input())
for test in range(t):
	n = int(input())
	colors = map(int, input().split())
	print(1, n)


for __ in range(int(input())):
	n = int(input())
	a = input()
	print(1, n)


def processing(array, n):
	return f'{1} {n}'
t = int(input())
while t > 0:
	n = int(input())
	array = [int(i) for i in input().split()]
	print(processing(array, n))
	t -= 1


for i in range(int(input())):
	n = int(input())
	k = [int(i) for i in input().split()]
	print(1, n)


for _ in range(int(input())):
	n = int(input())
	a = input()
	print(1, n)


def solve():
	n = int(input())
	arr = list(map(int, input().split()))
	print(1, len(arr))
	return
for _ in range(int(input())):
	solve()


t = int(input())
for p in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = []
	print(1, n)