1235 : 最大化子排列数组

Description

给定一个大小为 \(n\) 的排列 \(p\)。你希望最大化 \(p\) 中子排列数组的数量，为了实现这一目标，你打算执行一次以下操作：

• 选择两个整数 \(i\)，\(j\)，其中 \(1\le i,j\le n\)
• 然后交换 \(p_i\) 和 \(p_j\)。

例如，如果 \(p=[5,1,4,2,3]\)，我们选择 \(i=2\)，\(j=3\)，则结果数组将变为 \([5,4,1,2,3]\)。如果我们选择 \(i=j=5\)，则结果数组将保持不变，仍为 \([5,1,4,2,3]\)。

请选择合适 \(i\) 和 \(j\) 来最大化子排列数组的数量。

注意:

• 长度为 \(n\) 的排列是一个由 \(1\) 到 \(n\) 的 \(n\) 个不同整数以任意顺序组成的数组。例如，\([2,3,1,5,4]\) 是一个排列，但 \([1,2,2]\) 不是一个排列（出现了重复的 \(2\)），\([1,3,4]\) 也不是一个排列（\(n=3\) 但数组中有 \(4\)）。

• 数组 \(a\) 是数组 \(b\) 的子数组，当且仅当 \(a\) 可以通过从 \(b\) 中的开头和结尾删除一些（可能是零个或全部）元素而得到。

• 数组 \(a\) 是数组 \(b\) 的子排列数组，当且仅当 \(a\) 是一个排列，并且 \(a\) 是 \(b\) 的一个子数组。

Input

输入的第一行包含一个整数 \(t\ (1\le t\le 10)\) — 表示测试用例的数量。接下来是每个测试用例的描述。

每个测试用例的第一行包含一个整数 \(n\ (1\le n\le 10^6)\) — 表示排列的大小。

每个测试用例的下一行包含 \(n\) 个整数 \(p_1,p_2,\cdots p_n\)（\(1\le p_i\le n\)，所有的 \(p_i\) 互不相同）— 表示排列 \(p\) 的元素。

Output

对于每个测试用例，输出两个整数 \(i\) 和 \(j\)（\(1\le i,j \le n\)）— 表示在 \(p\) 中要交换的下标。

如果有多个解，输出其中任意一个即可。

Sample

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

3 3
1 2
1 4
1 3
9 9
4 9
2 4
1 5

Hint

Source

Author

SYSU