明人厌倦了在银行当一名简单的锁匠,所以他决定进入魔法学院,成为世界上最好的巫师!然而,为了入学,他需要解决考试中的一个问题,而这位雄心勃勃的英雄却无法做到这一点。
在这个问题中,他得到了一个长度为$$$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$$$) — 应该选择的子数组的边界,以便在应用该咒语后,数组中的反转数量最小化。
如果有多个合适的边界对,您可以输出其中任何一个。
示例
输入复制
971 4 3 2 5 3 361 4 3 2 5 387 6 5 8 4 3 2 1101 1 1 5 1 1 5 6 7 821337 6942 1 2 13998 244 35331 2 191 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$$$ 的段的任何操作只会增加反转次数。