#P18437. Yet Another Maximize Permutation Subarrays
Yet Another Maximize Permutation Subarrays
Yet Another Maximize Permutation Subarrays
给定一个长度为 的排列 。你希望使 中自身也是排列的子数组数量尽可能多。为此,你必须恰好执行一次以下操作:
- 选择两个整数 ,满足 。
- 交换 和 。
允许 ,此时排列不变。例如,,选择 后得到 ;选择 后,排列仍为 。
请输出一对使上述数量达到最大值的下标 。
长度为 的排列是将整数 各使用一次、按任意顺序排列得到的数组。例如, 是排列, 不是排列,因为 出现了两次; 也不是排列,因为长度为 ,却包含 。
子数组是原数组的一段连续元素,可以通过从原数组开头和结尾分别删除若干个元素得到。因此,这里统计的是那些恰好包含 的长度为 的连续子数组。
输入格式
第一行包含一个整数 (),表示测试用例数。
对于每个测试用例:
- 第一行包含一个整数 (),表示排列长度。
- 第二行包含 个整数 (,且两两不同)。
原题没有另外规定各测试用例的 之和上限。
输出格式
对于每个测试用例,输出两个整数 (),表示要交换的两个原数组位置。若最优方案有多个,输出任意一个。
原样例
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