B. Minimize Permutation Subarrays

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

You are given a permutation pp of size nn. You want to minimize the number of subarrays of pp that are permutations. In order to do so, you must perform the following operation exactly once:

• Select integers ii, jj, where 1≤i,j≤n1≤i,j≤n, then
• Swap pipi and pjpj.

For example, if p=[5,1,4,2,3]p=[5,1,4,2,3] and we choose i=2i=2, j=3j=3, the resulting array will be [5,4,1,2,3][5,4,1,2,3]. If instead we choose i=j=5i=j=5, the resulting array will be [5,1,4,2,3][5,1,4,2,3].

Which choice of ii and jj will minimize the number of subarrays that are permutations?

A permutation of length nn is an array consisting of nn distinct integers from 11 to nn in arbitrary order. For example, [2,3,1,5,4][2,3,1,5,4] is a permutation, but [1,2,2][1,2,2] is not a permutation (22 appears twice in the array), and [1,3,4][1,3,4] is also not a permutation (n=3n=3 but there is 44 in the array).

An array aa is a subarray of an array bb if aa can be obtained from bb by the deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end.

Input

The first line of the input contains a single integer tt (1≤t≤1041≤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 nn (3≤n≤2?1053≤n≤2?105) — the size of the permutation.

The next line of each test case contains nn integers p1,p2,…pnp1,p2,…pn (1≤pi≤n1≤pi≤n, all pipi are distinct) — the elements of the permutation pp.

It is guaranteed that the sum of nn over all test cases does not exceed 2?1052?105.

Output

For each test case, output two integers ii and jj (1≤i,j≤n1≤i,j≤n)  — the indices to swap in pp.

If there are multiple solutions, print any of them.

Example

input

Copy

8

3

1 2 3

3

1 3 2

5

1 3 2 5 4

6

4 5 6 1 2 3

9

8 7 6 3 2 1 4 5 9

10

7 10 5 1 9 8 3 2 6 4

10

8 5 10 9 2 1 3 4 6 7

10

2 3 5 7 10 1 8 6 4 9

output

Copy

2 3
1 1
5 2
1 4
9 5
8 8
6 10
5 4

Note

For the first test case, there are four possible arrays after the swap:

• If we swap p1p1 and p2p2, we get the array [2,1,3][2,1,3], which has 3 subarrays that are permutations ([1][1], [2,1][2,1], [2,1,3][2,1,3]).
• If we swap p1p1 and p3p3, we get the array [3,2,1][3,2,1], which has 3 subarrays that are permutations ([1][1], [2,1][2,1], [3,2,1][3,2,1]).
• If we swap p2p2 and p3p3, we get the array [1,3,2][1,3,2], which has 2 subarrays that are permutations ([1][1], [1,3,2][1,3,2]).
• If we swap any element with itself, we get the array [1,2,3][1,2,3], which has 3 subarrays that are permutations ([1][1], [1,2][1,2], [1,2,3][1,2,3]).

So the best swap to make is positions 22 and 33.

For the third sample case, after we swap elements at positions 22 and 55, the resulting array is [1,4,2,5,3][1,4,2,5,3]. The only subarrays that are permutations are [1][1] and [1,4,2,5,3][1,4,2,5,3]. We can show that this is minimal.

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int t;
    cin >> t;
    while(t--)
    {
        int n;
        cin >> n;
        int a[n+1];
        int p1, p2, pn;
        for(int i = 1; i <= n; i++)
        {
            cin >> a[i];
            if(a[i] == 1)
                p1 = i;
            else if(a[i] == 2)
                p2 = i;
            else if(a[i] == n)
                pn = i;
        }
        if((p1 < pn) && (p2 < pn))
            cout << pn << " " << max(p1,p2) <<endl;
        else if((p1 > pn) && (p2 > pn))
            cout << pn << " " << min(p1, p2)<<endl;
        else
            cout <<p1 << " " << p1 << endl;

    }
    return 0;
}