题目描述

Akito 厌倦了在银行当普通锁匠，于是决定进入魔法学院，成为世界上最厉害的巫师。为了入学，他需要解决考试中的一道题。

给定一个长度为 $n$ 的数组 $a$。你需要恰好施放一次魔法：选择两个整数 $l,r$，满足 $1\le l\le r\le n$，然后将子数组 $a_l,a_{l+1},\ldots,a_r$ 循环左移一位。

也就是说，原数组

$$[a_1,a_2,\ldots,a_{l-1},a_l,a_{l+1},\ldots,a_{r-1},a_r,a_{r+1},\ldots,a_n]$$

会变成

$$[a_1,a_2,\ldots,a_{l-1},a_{l+1},a_{l+2},\ldots,a_r,a_l,a_{r+1},\ldots,a_n].$$

你的目标是选择 $l,r$，使施法后数组中的逆序对数量最少。

长度为 $m$ 的数组 $b$ 中，一个逆序对指一对下标 $(i,j)$，满足 $1\le i<j\le m$ 且 $b_i>b_j$。例如，在数组 $[3,1,4,1,5]$ 中，逆序对为 $(1,2)$、$(1,4)$、$(3,4)$。

输入格式

第一行输入一个整数 $t$，表示测试用例数。

每个测试用例包含两行：

• 第一行输入一个整数 $n$，表示数组长度；
• 第二行输入 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

输出格式

对于每个测试用例，输出两个整数 $l$ 和 $r$，表示应选择的子数组边界。

如果有多组最优答案，输出任意一组即可。

输入输出样例

输入

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

说明/提示

第一个样例中，选择 $l=2,r=7$ 后，数组变为 $[1,3,2,5,3,3,4]$，其中逆序对数量为 $4$。可以证明无法得到更少的逆序对。

第二个样例中，选择 $l=2,r=4$ 后，数组变为 $[1,3,2,4,5,3]$，逆序对数量为 $3$。选择 $l=2,r=6$ 也同样最优。

第四个样例中，选择 $l=4,r=6$ 后，数组变为 $[1,1,1,1,1,5,5,6,7,8]$，数组已经有序。

最后一个样例中，数组一开始就是有序的，此时任意长度至少为 $2$ 的操作都会增加逆序对数量，因此可以选择长度为 $1$ 的区间。

数据范围

• $1\le t\le 10^4$；
• $1\le n\le 2000$；
• $1\le a_i\le 2000$；
• 所有测试用例的 $n^2$ 之和不超过 $4\cdot 10^6$。

时间限制：$2\text{s}$，空间限制：$256\text{MB}$。