CF1863B.Split Sort
普及/提高-
通过率:0%
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
You are given a permutation † p1,p2,…,pn of integers 1 to n .
You can change the current permutation by applying the following operation several (possibly, zero) times:
- choose some x ( 2≤x≤n );
- create a new permutation by:
- first, writing down all elements of p that are less than x , without changing their order;
- second, writing down all elements of p that are greater than or equal to x , without changing their order;
- replace p with the newly created permutation.
For example, if the permutation used to be [6,4,3,5,2,1] and you choose x=4 , then you will first write down [3,2,1] , then append this with [6,4,5] . So the initial permutation will be replaced by [3,2,1,6,4,5] .
Find the minimum number of operations you need to achieve pi=i for i=1,2,…,n . We can show that it is always possible to do so.
† 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).
输入格式
Each test contains multiple test cases. The first line contains the number of test cases t ( 1≤t≤1000 ). The description of the test cases follows.
The first line of each test case contains one integer n ( 1≤n≤100000 ).
The second line of each test case contains n integers p1,p2,…,pn ( 1≤pi≤n ). It is guaranteed that p1,p2,…,pn is a permutation.
It is guaranteed that the sum of n over all test cases does not exceed 100000 .
输出格式
For each test case, output the answer on a separate line.
输入输出样例
输入#1
5 1 1 2 2 1 6 6 4 3 5 2 1 3 3 1 2 19 10 19 7 1 17 11 8 5 12 9 4 18 14 2 6 15 3 16 13
输出#1
0 1 4 1 7
说明/提示
In the first test case, n=1 and p1=1 , so there is nothing left to do.
In the second test case, we can choose x=2 and we immediately obtain p1=1 , p2=2 .
In the third test case, we can achieve the minimum number of operations in the following way:
- x=4 : [6,4,3,5,2,1]→[3,2,1,6,4,5] ;
- x=6 : [3,2,1,6,4,5]→[3,2,1,4,5,6] ;
- x=3 : [3,2,1,4,5,6]→[2,1,3,4,5,6] ;
- x=2 : [2,1,3,4,5,6]→[1,2,3,4,5,6] .