← 返回题目列表

Codeforces · 2072/D

D. 对于巫师来说,考试很简单,但我却应付不了

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

明人厌倦了在银行当一名简单的锁匠,所以他决定进入魔法学院,成为世界上最好的巫师!然而,为了入学,他需要解决考试中的一个问题,而这位雄心勃勃的英雄却无法做到这一点。

在这个问题中,他得到了一个长度为$$$n$$$的数组$$$a$$$。他需要在应用咒语后最小化数组中的反转次数$$$^{\text{*}}$$$ 正好一次。这个咒语很简单;为了应用它,Akito 必须选择两个数字 $$$l$$$ 和 $$$r$$$ 使得 $$$1 \le l \le r \le n$$$ 并对子数组进行循环移位,从 $$$l$$$ 到 $$$r$$$ 向左移动一个位置。

更正式地说,Akito 选择子数组 $$$[l, r]$$$ 并修改该数组如下:

  • 来自原始数组 $$$[a_1, a_2, \ldots, a_{l - 1}, \mathbf{ a_l }, \mathbf{ a_{l + 1} } , \mathbf{ \ldots }, \mathbf{ a_{r - 1} }, \mathbf{ a_r }, a_{r + 1}, \ldots, a_{n - 1}, a_n]$$$,他得到数组 $$$[a_1, a_2, \ldots, a_{l - 1}, \mathbf{ a_{l + 1} }, \mathbf{ a_{l + 2} }, \mathbf{ \ldots }, \mathbf{ a_{r - 1} }、\mathbf{a_{r}}、\mathbf{a_{l}}、a_{r + 1}、\ldots、a_{n - 1}、a_{n}]$$$。

Akito 渴望开始学习,但他仍然没有通过考试。帮助他注册并解决问题!

$$$^{\text{*}}$$$长度为$$$m$$$的数组$$$b$$$中的反转被定义为一对索引$$$(i, j)$$$,使得$$$1 \le i \lt j \le m$$$和$$$b_i \gt b_j$$$。例如,在数组 $$$b = [3, 1, 4, 1, 5]$$$ 中,反转是索引对 $$$(1, 2)$$$、$$$(1, 4)$$$、$$$(3, 4)$$$。

输入

输入的第一行包含一个数字 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

在每个测试用例的第一行,有一个数字 $$$n$$$ ($$$1 \le n \le 2000$$$) — 数组 $$$a$$$ 的长度。

在每个测试用例的第二行中,有 $$$n$$$ 数字 $$$a_i$$$ ($$$1 \le a_i \le 2000$$$) — 数组 $$$a$$$ 的元素。

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

输出

对于每个测试用例,输出两个数字 $$$l$$$ 和 $$$r$$$ ($$$1 \le l \le r \le n$$$) — 应该选择的子数组的边界,以便在应用该咒语后,数组中的反转数量最小化。

如果有多个合适的边界对,您可以输出其中任何一个。

示例

输入
复制

9
7
1 4 3 2 5 3 3
6
1 4 3 2 5 3
8
7 6 5 8 4 3 2 1
10
1 1 1 5 1 1 5 6 7 8
2
1337 69
4
2 1 2 1
3
998 244 353
3
1 2 1
9
1 1 2 3 5 8 13 21 34

输出
复制

2 7
2 4
1 8
4 6
1 2
1 4
1 3
2 3
5 5

注意

在第一个示例中,数组 $$$[1, 4, 3, 2, 5, 3, 3]$$$ 将变成数组 $$$[1, 3, 2, 5, 3, 3, 4]$$$。其中的反转是 $$$(2, 3)$$$、$$$(4, 5)$$$、$$$(4, 6)$$$ 和 $$$(4, 7)$$$。可以证明,不可能实现少于 $$$4$$$ 的反转。

在第二个示例中,数组 $$$[1, 4, 3, 2, 5, 3]$$$ 将变成 $$$[1, 3, 2, 4, 5, 3]$$$。其中的反转是 $$$(2, 3)$$$、$$$(4, 6)$$$ 和 $$$(5, 6)$$$。 $$$l = 2$$$ 和 $$$r = 6$$$ 也有效,那么数组将变成 $$$[1, 3, 2, 5, 3, 4]$$$,其中还有 $$$3$$$ 反转 — $$$(2, 3)$$$、$$$(4, 5)$$$ 和 $$$(4, 6)$$$。可以证明,不可能实现少于 $$$3$$$ 的反转。

在第四个示例中,选择 $$$l = 4$$$ 和 $$$r = 6$$$ 将数组转换为 $$$[1, 1, 1, 1, 1, 5, 5, 6, 7, 8]$$$。它已排序,因此不存在反转。

在最后一个示例中,数组最初是排序的,因此对长度至少为 $$$2$$$ 的段的任何操作只会增加反转次数。