You are given an array $a_1, a_2, \ldots, a_n$ of positive integers. A good pair is a pair of indices $(i, j)$ with $1 \leq i, j \leq n$ such that, for all $1 \leq k \leq n$, the following equality holds:

$$ |a_i - a_k| + |a_k - a_j| = |a_i - a_j|, $$ where $|x|$ denotes the absolute value of $x$.

Find a good pair. Note that $i$ can be equal to $j$.


-----Input-----

The input consists of multiple test cases. The first line contains a single integer $t$ ($1 \leq t \leq 1000$) — the number of test cases. Description of the test cases follows.

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

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq 10^9$) where $a_i$ is the $i$-th element of the array.

The sum of $n$ for all test cases is at most $2 \cdot 10^5$.


-----Output-----

For each test case, print a single line with two space-separated indices $i$ and $j$ which form a good pair of the array. The case $i=j$ is allowed. It can be shown that such a pair always exists. If there are multiple good pairs, print any of them.


-----Examples-----

Input
3
3
5 2 7
5
1 4 2 2 3
1
2
Output
2 3
1 2
1 1


-----Note-----

In the first case, for $i = 2$ and $j = 3$ the equality holds true for all $k$:

$k = 1$: $|a_2 - a_1| + |a_1 - a_3| = |2 - 5| + |5 - 7| = 5 = |2 - 7| = |a_2-a_3|$,

$k = 2$: $|a_2 - a_2| + |a_2 - a_3| = |2 - 2| + |2 - 7| = 5 = |2 - 7| = |a_2-a_3|$,

$k = 3$: $|a_2 - a_3| + |a_3 - a_3| = |2 - 7| + |7 - 7| = 5 = |2 - 7| = |a_2-a_3|$.

Difficulty: EASY
Tags: Sorting

Mathematics
Skill types: Sorting

Starter code:

Solutions:
t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	(mn, mx) = (l.index(min(l)), l.index(max(l)))
	print(mn + 1, mx + 1)


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	l = []
	l.append(a.index(min(a)) + 1)
	l.append(a.index(max(a)) + 1)
	print(*l)


import sys
test_case = int(sys.stdin.readline())
for repeat in range(test_case):
	length = int(sys.stdin.readline())
	num_list = list(map(int, sys.stdin.readline().split()))
	print('%d %d' % (num_list.index(min(num_list)) + 1, num_list.index(max(num_list)) + 1))


T = int(input())
for _ in range(T):
	n = int(input())
	a = list(map(int, input().split()))
	i = a.index(min(a)) + 1
	j = a.index(max(a)) + 1
	print(i, j)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	a = l.index(max(l))
	b = l.index(min(l))
	print(a + 1, b + 1)


for _ in range(int(input())):
	x = input().split()
	y = list(map(int, input().split()))
	if len(y) == 1:
		print(1, 1)
	else:
		print(y.index(min(y)) + 1, y.index(max(y)) + 1)


tc = int(input())
for i in range(tc):
	x = int(input())
	y = list(map(int, input().split()))
	print(y.index(min(y)) + 1, y.index(max(y)) + 1)


def main():
	T = int(input())
	for k in range(T):
		n = int(input())
		array = list(map(int, input().split(' ')))
		min_elem = min(array)
		max_elem = max(array)
		min_elem_pos = array.index(min_elem)
		max_ele_pos = array.index(max_elem)
		print(f'{min_elem_pos + 1} {max_ele_pos + 1}')
main()


t = int(input())
while t:
	t -= 1
	n = int(input())
	a = list(map(int, input().split()))
	x = min(a)
	x1 = max(a)
	i = a.index(x) + 1
	j = a.index(x1) + 1
	print(i, j)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	x = a.index(max(a))
	y = a.index(min(a))
	print(y + 1, x + 1)


a = int(input())
for i in range(a):
	b = int(input())
	c = list(map(int, input().split()))
	print(c.index(max(c)) + 1, c.index(min(c)) + 1)


p = lambda a: print(a)
iip = lambda : int(input())
sip = lambda : input()
mip = lambda : map(int, input().strip().split())
lip = lambda : list(map(int, input().strip().split()))
ceil = lambda x: int(x) if x == int(x) else int(x) + 1
flr = lambda x: int(x)
tstcs = lambda : range(int(input()))
for t in tstcs():
	n = iip()
	a = lip()
	print(a.index(min(a)) + 1, a.index(max(a)) + 1)


T = int(input())
for _ in range(T):
	_ = input()
	A = list(map(int, input().split()))
	(a, b) = (A.index(max(A)), A.index(min(A)))
	if a < b:
		print(a + 1, b + 1)
	else:
		print(b + 1, a + 1)


t = int(input())
while t:
	n = int(input())
	x = list(map(int, input().split()))
	if n == 1:
		print(1, 1)
	else:
		x1 = x.index(max(x)) + 1
		x2 = x.index(min(x)) + 1
		print(min(x1, x2), max(x1, x2))
	t = t - 1


t = int(input())
for i in range(t):
	n = int(input())
	li = list(map(int, input().split()))
	if n > 2:
		print(li.index(min(li)) + 1, li.index(max(li)) + 1)
	elif n == 1:
		print('1 1')
	else:
		print('1 2')


for i in range(int(input())):
	input()
	li = list(map(int, input().split()))
	print(li.index(min(li)) + 1, li.index(max(li)) + 1)


a = int(input())
d = 0
for _ in range(a):
	b = int(input())
	c = list(map(int, input().split()))
	print(c.index(min(c)) + 1, c.index(max(c)) + 1)


t = int(input())
while t > 0:
	n = int(input())
	a = [int(ele) for ele in input().split(' ')]
	M = max(a)
	m = min(a)
	print(a.index(m) + 1, a.index(M) + 1)
	t -= 1


for i in range(int(input())):
	ab = int(input())
	abc = list(map(int, input().split()))
	print(abc.index(min(abc)) + 1, abc.index(max(abc)) + 1)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	min_i = a.index(min(a))
	max_i = a.index(max(a))
	print(1 + min_i, 1 + max_i)


for q in range(int(input())):
	n = int(input())
	arr = [int(x) for x in input().split()]
	print(arr.index(min(arr)) + 1, arr.index(max(arr)) + 1)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	if n == 1:
		print(1, 1)
	else:
		print(l.index(max(l)) + 1, l.index(min(l)) + 1)


n = int(input())
for i in range(n):
	m = int(input())
	a = list(map(int, input().split()))
	print(a.index(min(a)) + 1, a.index(max(a)) + 1)


for te in [0] * int(input()):
	input()
	r = [*map(int, input().split())]
	print(r.index(min(r)) + 1, r.index(max(r)) + 1)


def fun(a):
	m = max(a)
	idx = a.index(m)
	m = min(a)
	return [a.index(m) + 1, idx + 1]
for _ in range(int(input())):
	x = int(input())
	a = input().split()
	a = list(map(int, a))
	print(*fun(a))


for _ in range(int(input())):
	(N, A) = (int(input()), list(map(int, input().split(' '))))
	print(A.index(min(A)) + 1, A.index(max(A)) + 1)


import math
t = int(input())
while t:
	n = int(input())
	a = list(map(int, input().split()))
	l = []
	if len(a) == 1:
		l.append(1)
		l.append(1)
	else:
		mn = min(a)
		mx = max(a)
		l.append(a.index(mn) + 1)
		l.append(a.index(mx) + 1)
	print(*l)
	t -= 1


for i in range(int(input())):
	lenn = int(input())
	list1 = list(map(int, input().split()))
	print(list1.index(min(list1)) + 1, list1.index(max(list1)) + 1)


def answer():
	t = int(input())
	for i in range(t):
		n = int(input())
		arr = list(map(int, input().split()))
		x = arr.index(min(arr)) + 1
		y = arr.index(max(arr)) + 1
		print(x, y)
answer()


for i in range(int(input())):
	n = int(input())
	l1 = list(map(int, input().split()))
	print(l1.index(min(l1)) + 1, l1.index(max(l1)) + 1)


x = int(input())
for i in range(x):
	y = input()
	a = list(map(int, input().strip().split()))
	print(a.index(min(a)) + 1, a.index(max(a)) + 1)


import sys
input = lambda : sys.stdin.readline()[:-1]
ni = lambda : int(input())
na = lambda : list(map(int, input().split()))
yes = lambda : print('yes')
Yes = lambda : print('Yes')
YES = lambda : print('YES')
no = lambda : print('no')
No = lambda : print('No')
NO = lambda : print('NO')
T = ni()
for _ in range(T):
	n = ni()
	a = na()
	print(a.index(min(a)) + 1, a.index(max(a)) + 1)


t = int(input())

def f(l):
	maxi = max(l)
	mini = min(l)
	l = [l.index(maxi) + 1, l.index(mini) + 1]
	l.sort()
	return l
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	(i, j) = f(l)
	print(i, j)


n = int(input())
lengths = []
arrays = []
for _ in range(n):
	length = int(input())
	lengths.append(length)
	array = list(map(int, input().split()))
	arrays.append(array)
for arr in arrays:
	i = arr.index(max(arr)) + 1
	j = arr.index(min(arr)) + 1
	print(i, j)


case = int(input())
while case > 0:
	num = int(input())
	arr = list(map(int, input().split()))
	if num == 1:
		print(1, end=' ')
		print(1)
		case -= 1
		continue
	maxS = max(arr)
	minS = min(arr)
	a = arr.index(maxS)
	i = arr.index(minS)
	if a < i:
		print('%d %d' % (a + 1, i + 1))
	else:
		print('%d %d' % (i + 1, a + 1))
	case -= 1


t = int(input())
while t > 0:
	n = int(input())
	k = list(map(int, input().split()))
	i = min(k)
	j = max(k)
	print(k.index(i) + 1, k.index(j) + 1)
	t = t - 1


t = int(input())
while t > 0:
	n = int(input())
	x = input()
	x = x.split(' ')
	x = list(map(int, x))
	print(x.index(min(x)) + 1, x.index(max(x)) + 1)
	t -= 1


import sys
import math
mod = 10 ** 9 + 7

def ri():
	return int(input())

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

def rls():
	return list(map(str, input().split()))

def rm():
	return map(int, input().split())

def isPowerOfTwo(x):
	return x and (not x & x - 1)

def decimalToBinary(n):
	return bin(n).replace('0b', '')
for _ in range(ri()):
	n = ri()
	l = rl()
	a = l.index(max(l)) + 1
	b = l.index(min(l)) + 1
	print(b, a)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	try:
		d = l[1] - l[0]
	except:
		print(1, 1)
	else:
		print(l.index(min(l)) + 1, l.index(max(l)) + 1)


try:
	t = int(input())
	while t:
		n = int(input())
		arr = list(map(int, input().split()))
		mx = max(arr)
		mn = min(arr)
		ans1 = arr.index(mn)
		ans2 = arr.index(mx)
		print(ans1 + 1, ans2 + 1)
except:
	pass


for _ in range(int(input())):
	a = int(input())
	l = list(map(int, input().split()))
	k = l.index(max(l))
	p = l.index(min(l))
	if k > p:
		print(p + 1, k + 1)
	else:
		print(k + 1, p + 1)


t = 0
try:
	t = int(input())
except:
	pass
while t > 0:
	t = t - 1
	n = int(input())
	arr = map(int, input().split())
	arr = list(arr)
	first = arr.index(max(arr)) + 1
	second = arr.index(min(arr)) + 1
	if first < second:
		print(first, end=' ')
		print(second)
	else:
		print(second, end=' ')
		print(first)


t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	lmax = max(l)
	lmin = min(l)
	i = l.index(lmax)
	j = l.index(lmin)
	if i <= j:
		print(i + 1, ' ', j + 1)
	else:
		print(j + 1, ' ', i + 1)


def solver():
	n = int(input())
	for _ in range(n):
		l = int(input())
		x = list(map(int, input().split()))
		print(x.index(min(x)) + 1, x.index(max(x)) + 1)
solver()


for _ in range(int(input())):
	n = int(input())
	ar = list(map(int, input().split()))
	a = max(ar)
	b = min(ar)
	c = ar.index(a) + 1
	d = ar.index(b) + 1
	print(f'{d} {c}')


t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(a) for a in input().split()]
	input_dict = {}
	fin_max = a.index(max(a)) + 1
	fin_min = a.index(min(a)) + 1
	print(fin_min, fin_max)


for i in range(int(input())):
	input()
	items = [*map(int, input().split())]
	print(items.index(min(items)) + 1, items.index(max(items)) + 1)


t = int(input())
for i in range(t):
	l = int(input())
	a = list(map(int, input().split()))
	print(a.index(min(a)) + 1, a.index(max(a)) + 1)


test = int(input())
for i in range(test):
	length = int(input())
	arr = list(map(int, input().split()))
	print(arr.index(min(arr)) + 1, arr.index(max(arr)) + 1)


t = int(input())
for n in range(t):
	k = int(input())
	l = list(map(int, input().split(' ')))
	i = l.index(max(l))
	j = l.index(min(l))
	print(j + 1, i + 1)


for _ in range(int(input())):
	f = input()
	x = list(map(int, input().split()))
	print(x.index(min(x)) + 1, x.index(max(x)) + 1)


for _ in range(int(input())):
	l = int(input())
	ar = list(map(int, input().split()))
	mx = ar.index(max(ar))
	mn = ar.index(min(ar))
	if mx > mn:
		print(mn + 1, mx + 1)
	else:
		print(mn + 1, mx + 1)


num = int(input())
for i in range(num):
	n = int(input())
	arr = input().split()
	arr = list(map(int, arr))
	a = arr.index(min(arr))
	b = arr.index(max(arr))
	print(a + 1, b + 1)


for t in range(int(input())):
	n = int(input())
	st = list(map(int, input().split()))
	print(st.index(min(st)) + 1, st.index(max(st)) + 1)


for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	print(a.index(min(a)) + 1, a.index(max(a)) + 1)


for _ in range(int(input())):
	n = int(input())
	lst = list(map(int, input().split(' ')))
	if n == 1:
		print('1 1')
	else:
		i = lst.index(min(lst)) + 1
		j = lst.index(max(lst)) + 1
		print(str(i) + ' ' + str(j))


for _ in range(int(input())):
	length = int(input())
	l = list(map(int, input().split()))
	print(l.index(min(l)) + 1, l.index(max(l)) + 1)


for i in range(int(input())):
	A = int(input())
	B = list(map(int, input().split()))
	if len(B) > 1:
		print(B.index(min(B)) + 1, B.index(max(B)) + 1)
	else:
		print('1' + ' ' + '1')


t = int(input())
for i in range(t):
	n = int(input())
	lst = list(map(int, input().split()))
	print(lst.index(min(lst)) + 1, lst.index(max(lst)) + 1)


num = int(input())
for i in range(0, num):
	n = int(input())
	l = list(map(int, input().split(' ')))
	m = max(l)
	m1 = min(l)
	ind1 = l.index(m)
	ind2 = l.index(m1)
	print(ind2 + 1, ind1 + 1)


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	mi = a.index(min(a)) + 1
	ma = a.index(max(a)) + 1
	print(mi, ma)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	mn = min(a)
	mx = max(a)
	print(a.index(mn) + 1, a.index(mx) + 1)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	print(*sorted([l.index(max(l)) + 1, l.index(min(l)) + 1]))


for T in range(int(input())):
	n = int(input())
	A = list(map(int, input().split()))
	mn = 1000000000.0 + 1
	mx = 0
	i_mn = -1
	i_mx = -1
	for i in range(n):
		if A[i] < mn:
			mn = A[i]
			i_mn = i
		if A[i] > mx:
			mx = A[i]
			i_mx = i
	print(i_mn + 1, i_mx + 1)


from collections import deque
t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(_) for _ in input().split()]
	print(a.index(min(a)) + 1, a.index(max(a)) + 1)


import sys
input = sys.stdin.readline

def solve(n, arr):
	(mi, ma) = (float('inf'), -float('inf'))
	mii = mai = 0
	for i in range(n):
		if mi > arr[i]:
			mi = arr[i]
			mii = i
		if ma < arr[i]:
			ma = arr[i]
			mai = i
	print(mii + 1, mai + 1)
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	solve(n, arr)


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split(' ')))
	min_a = min(a)
	max_a = max(a)
	min_ind = a.index(min_a)
	max_ind = a.index(max_a)
	print(min_ind + 1, max_ind + 1)


t = int(input())
for i in range(t):
	n = int(input())
	lst = list(map(int, input().split()))
	if n == 1:
		print(1, 1)
	else:
		mi = lst.index(min(lst))
		ma = lst.index(max(lst))
		print(mi + 1, ma + 1)


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	print(a.index(min(a)) + 1, a.index(max(a)) + 1)


def Solve():
	n = int(input())
	a = list(map(int, input().split()))
	smin = min(a)
	smax = max(a)
	i = a.index(smin)
	j = a.index(smax)
	print(i + 1, j + 1)
q = int(input())
while q > 0:
	Solve()
	q = q - 1


t = int(input())
for i in range(t):
	n = int(input())
	a = [int(x) for x in input().split(' ')]
	print(a.index(min(a)) + 1, end=' ')
	print(a.index(max(a)) + 1)