← 返回题目列表

Codeforces · 1838/B

B. 最小化排列子数组

中文机器翻译题面 查看原题

给你一个大小为 $$$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]$$$。我们可以证明这是最小的。