#P18437. Yet Another Maximize Permutation Subarrays

Yet Another Maximize Permutation Subarrays

Yet Another Maximize Permutation Subarrays

给定一个长度为 nn 的排列 pp。你希望使 pp 中自身也是排列的子数组数量尽可能多。为此,你必须恰好执行一次以下操作:

  • 选择两个整数 i,ji,j,满足 1≤i,j≤n1\le i,j\le n。
  • 交换 pip_i 和 pjp_j。

允许 i=ji=j,此时排列不变。例如,p=[5,1,4,2,3]p=[5,1,4,2,3],选择 i=2,j=3i=2,j=3 后得到 [5,4,1,2,3][5,4,1,2,3];选择 i=j=5i=j=5 后,排列仍为 [5,1,4,2,3][5,1,4,2,3]。

请输出一对使上述数量达到最大值的下标 i,ji,j。

长度为 kk 的排列是将整数 1,2,…,k1,2,\ldots,k 各使用一次、按任意顺序排列得到的数组。例如,[2,3,1,5,4][2,3,1,5,4] 是排列,[1,2,2][1,2,2] 不是排列,因为 22 出现了两次;[1,3,4][1,3,4] 也不是排列,因为长度为 33,却包含 44。

子数组是原数组的一段连续元素,可以通过从原数组开头和结尾分别删除若干个元素得到。因此,这里统计的是那些恰好包含 1,2,…,k1,2,\ldots,k 的长度为 kk 的连续子数组。

输入格式

第一行包含一个整数 tt(1≤t≤101\le t\le10),表示测试用例数。

对于每个测试用例:

  • 第一行包含一个整数 nn(1≤n≤1061\le n\le10^6),表示排列长度。
  • 第二行包含 nn 个整数 p1,p2,…,pnp_1,p_2,\ldots,p_n(1≤pi≤n1\le p_i\le n,且两两不同)。

原题没有另外规定各测试用例的 nn 之和上限。

输出格式

对于每个测试用例,输出两个整数 i,ji,j(1≤i,j≤n1\le i,j\le n),表示要交换的两个原数组位置。若最优方案有多个,输出任意一个。

原样例

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
3 3
1 2
1 4
1 3
9 9
4 9
2 4
1 5