CF1792C.Min Max Sort
普及/提高-
通过率:0%
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
You are given a permutation p of length n (a permutation of length n is an array of length n in which each integer from 1 to n occurs exactly once).
You can perform the following operation any number of times (possibly zero):
- choose two different elements x and y and erase them from the permutation;
- insert the minimum of x and y into the permutation in such a way that it becomes the first element;
- insert the maximum of x and y into the permutation in such a way that it becomes the last element.
For example, if p=[1,5,4,2,3] and we want to apply the operation to the elements 3 and 5 , then after the first step of the operation, the permutation becomes p=[1,4,2] ; and after we insert the elements, it becomes p=[3,1,4,2,5] .
Your task is to calculate the minimum number of operations described above to sort the permutation p in ascending order (i. e. transform p so that p1<p2<⋯<pn ).
输入格式
The first line contains a single integer t ( 1≤t≤104 ) — the number of test cases.
The first line of the test case contains a single integer n ( 1≤n≤2⋅105 ) — the number of elements in the permutation.
The second line of the test case contains n distinct integers from 1 to n — the given permutation p .
The sum of n over all test cases doesn't exceed 2⋅105 .
输出格式
For each test case, output a single integer — the minimum number of operations described above to sort the array p in ascending order.
输入输出样例
输入#1
4 5 1 5 4 2 3 3 1 2 3 4 2 1 4 3 6 5 2 4 1 6 3
输出#1
2 0 1 3
说明/提示
In the first example, you can proceed as follows:
- in the permutation p=[1,5,4,2,3] , let's choose the elements 4 and 2 , then, after applying the operation, the permutation becomes p=[2,1,5,3,4] ;
- in the permutation p=[2,1,5,3,4] , let's choose the elements 1 and 5 , then, after applying operation, the permutation becomes p=[1,2,3,4,5] .