给你一个大小为 $$$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$$$ 的排列是一个数组,由 $$$n$$$ 个从 $$$1$$$ 到 $$$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
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
输出 #1
2 3 1 1 5 2 1 4 9 5 8 8 6 10 5 4
注意
对于第一个测试用例,交换后有四个可能的数组:
- 如果我们交换 $$$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$$$ 和 $$$5$$$ 处的元素后,生成的数组为 $$$[1, 4, 2, 5, 3]$$$。唯一属于排列的子数组是 $$$[1]$$$ 和 $$$[1, 4, 2, 5, 3]$$$。我们可以证明这是最小的。