CF2072D.For Wizards, the Exam Is Easy, but I Couldn't Handle It

Akito 厌倦了在银行当普通锁匠的工作，因此他决定进入魔法学院并成为世界上最强的巫师！然而，为了入学，他需要解决考试中的唯一一道题目，而这位雄心勃勃的英雄却未能成功。

题目给出一个长度为 $n$ 的数组 $a$。Akito 需要在使用恰好一次咒语后，使数组中的逆序对数量 $^{\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$ 中，逆序对被定义为满足 $1 \le i < j \le m$ 且 $b_i > b_j$ 的索引对 $(i, 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$）——选择的子数组边界，使得应用咒语后数组的逆序对数量最小。

如果存在多个符合条件的边界对，可以输出其中任意一个。

在第一个示例中，数组 $[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$ 的段进行任何操作只会增加逆序对的数量。

翻译由 DeepSeek R1 完成