CF1838B Minimize Permutation Subarrays

给定一个长度为 $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 翻译