Good Pairs codeforces in cpp

 CodeTON Round 1 (Div. 1 + Div. 2, Rated, Prizes!)

A. Good Pairs

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

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

|ai−ak|+|ak−aj|=|ai−aj|,$$|a_i-a_k|+|a_k-a_j|=|a_i-a_j|,$$

where |x|$|x|$ denotes the absolute value of x$x$.

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

Input

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

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

The second line of each test case contains n$n$ integers a1,a2,…,an$a_1,a_2,\dots ,a_n$ (1≤ai≤109$1\le a_i\le {10}^9$) where ai$a_i$ is the i$i$-th element of the array.

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

Output

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

Example

input

Copy

3
3
5 2 7
5
1 4 2 2 3
1
2

output

Copy

2 3
1 2
1 1

Note

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

• k=1$k=1$: |a2−a1|+|a1−a3|=|2−5|+|5−7|=5=|2−7|=|a2−a3|$|a_2-a_1|+|a_1-a_3|=|2-5|+|5-7|=5=|2-7|=|a_2-a_3|$,
• k=2$k=2$: |a2−a2|+|a2−a3|=|2−2|+|2−7|=5=|2−7|=|a2−a3|$|a_2-a_2|+|a_2-a_3|=|2-2|+|2-7|=5=|2-7|=|a_2-a_3|$,
• k=3$k=3$: |a2−a3|+|a3−a3|=|2−7|+|7−7|=5=|2−7|=|a2−a3|$|a_2-a_3|+|a_3-a_3|=|2-7|+|7-7|=5=|2-7|=|a_2-a_3|$.

solution:

#include<iostream>
#include<algorithm>
#include<vector>
#define ll long long
using namespace std;
 
void solve()
{
	ll n;
	cin >> n;
	vector<int> v(n);
	for (ll i = 0; i < n; i++)
	{
		cin >> v[i];
	}
	ll minIndex = min_element(v.begin(), v.end()) - v.begin();
	ll maxIndex = max_element(v.begin(), v.end()) - v.begin();
	cout << minIndex+1 << " " << maxIndex+1 << "\n";
}
 
int main()
{
	int t;
	cin >> t;
	while (t--)
	{
		solve();
	}
	return 0;
}