题目描述

给定一个长度为 $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$ 的一个子数组。

输入格式

输入的第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。接下来是每个测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$3 \le n \le 2\cdot 10^5$），表示排列的长度。

接下来一行包含 $n$ 个整数 $p_1, p_2, \ldots, p_n$（$1 \le p_i \le n$，所有 $p_i$ 互不相同），表示排列 $p$ 的元素。

保证所有测试用例中 $n$ 的总和不超过 $2\cdot 10^5$。

输出格式

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

如果有多组解，输出任意一组均可。

说明/提示

对于第一个测试用例，交换后可能得到以下四种数组：

• 如果交换 $p_1$ 和 $p_2$，得到数组 $[2, 1, 3]$，其中有 3 个子数组为排列（$[1]$、$[2, 1]$、$[2, 1, 3]$）。
• 如果交换 $p_1$ 和 $p_3$，得到数组 $[3, 2, 1]$，其中有 3 个子数组为排列（$[1]$、$[2, 1]$、$[3, 2, 1]$）。
• 如果交换 $p_2$ 和 $p_3$，得到数组 $[1, 3, 2]$，其中有 2 个子数组为排列（$[1]$、$[1, 3, 2]$）。
• 如果任意元素与自身交换，得到数组 $[1, 2, 3]$，其中有 3 个子数组为排列（$[1]$、$[1, 2]$、$[1, 2, 3]$）。

因此，最佳的交换方式是位置 $2$ 和 $3$。对于第三个样例，交换第 $2$ 和第 $5$ 个元素后，得到数组 $[1, 4, 2, 5, 3]$，只有 $[1]$ 和 $[1, 4, 2, 5, 3]$ 这两个子数组为排列。可以证明这是最优的。

由 ChatGPT 4.1 翻译

样例

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

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