CSG-CPC
Online Judge

1235 : 最大化子排列数组

         Time Limit: 2 Sec     Memory Limit: 256 Mb     Submitted: 6     Solved: 2     SpecialJudge

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