CF1838B.Minimize Permutation Subarrays
普及/提高-
通过率:0%
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
You are given a permutation p of size n . You want to minimize the number of subarrays of p that are permutations. In order to do so, you must perform the following operation exactly once:
- Select integers i , j , where 1≤i,j≤n , then
- Swap pi and pj .
For example, if p=[5,1,4,2,3] and we choose i=2 , j=3 , the resulting array will be [5,4,1,2,3] . If instead we choose i=j=5 , the resulting array will be [5,1,4,2,3] .
Which choice of i and j will minimize the number of subarrays that are permutations?
A permutation of length n is an array consisting of n distinct integers from 1 to n in arbitrary order. For example, [2,3,1,5,4] is a permutation, but [1,2,2] is not a permutation ( 2 appears twice in the array), and [1,3,4] is also not a permutation ( n=3 but there is 4 in the array).
An array a is a subarray of an array b if a can be obtained from b by the deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end.
输入格式
The first line of the input contains a single integer t ( 1≤t≤104 ) — the number of test cases. The description of the test cases follows.
The first line of each test case contains a single integer n ( 3≤n≤2⋅105 ) — the size of the permutation.
The next line of each test case contains n integers p1,p2,…pn ( 1≤pi≤n , all pi are distinct) — the elements of the permutation p .
It is guaranteed that the sum of n over all test cases does not exceed 2⋅105 .
输出格式
For each test case, output two integers i and j ( 1≤i,j≤n ) — the indices to swap in p .
If there are multiple solutions, print any of them.
输入输出样例
输入#1
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
输出#1
2 3 1 1 5 2 1 4 9 5 8 8 6 10 5 4
说明/提示
For the first test case, there are four possible arrays after the swap:
- If we swap p1 and p2 , we get the array [2,1,3] , which has 3 subarrays that are permutations ( [1] , [2,1] , [2,1,3] ).
- If we swap p1 and p3 , we get the array [3,2,1] , which has 3 subarrays that are permutations ( [1] , [2,1] , [3,2,1] ).
- If we swap p2 and p3 , we get the array [1,3,2] , which has 2 subarrays that are permutations ( [1] , [1,3,2] ).
- If we swap any element with itself, we get the array [1,2,3] , which has 3 subarrays that are permutations ( [1] , [1,2] , [1,2,3] ).
So the best swap to make is positions 2 and 3 .For the third sample case, after we swap elements at positions 2 and 5 , the resulting array is [1,4,2,5,3] . The only subarrays that are permutations are [1] and [1,4,2,5,3] . We can show that this is minimal.