[Solution] End Sorted solution codechef

End Sorted solution codechef – Chef considers a permutation PP of {1,2,3,,N}{1,2,3,…,N} End Sorted if and only if P1=1P1=1 and PN=NPN=N.

Table of Contents

[Solution] End Sorted solution codechef

Chef is given a permutation PP.

In one operation Chef can choose any index i (1iN1)i (1≤i≤N−1) and swap PiPi and Pi+1Pi+1. Determine the minimum number of operations required by Chef to make the permutation PP End Sorted.

Note: An array PP is said to be a permutation of {1,2,3,,N}{1,2,3,…,N} if PP contains each element of {1,2,3,,N}{1,2,3,…,N} exactly once.

Input Format

  • The first line of input will contain a single integer TT, denoting the number of test cases.
  • Each test case consists of two lines of input.
    • The first line of each test case contains a single integer NN, denoting the length of the permutation PP.
    • The second line contains NN space-separated integers P1,P2,P3,,PNP1,P2,P3,…,PN, denoting the permutation PP.

[Solution] End Sorted solution codechef

For each test case, output minimum number of operations required by Chef to make the permutation PP End Sorted.

Constraints

  • 1T10001≤T≤1000
  • 2N1052≤N≤105
  • PP is a permutation of {1,2,3,N}{1,2,3,…N}
  • The sum of NN over all test cases does not exceed 31053⋅105.

Sample Input 1 

4
4
1 3 2 4
3
3 2 1
2
2 1
3
2 1 3

[Solution] End Sorted solution codechef

 

0
3
1
1

Explanation

Test case 11: PP is already End Sorted.

Test case 22: PP can be made End Sorted using 33 operations as follows: [3,2,1][2,3,1][2,1,3][1,2,3][3,2,1]→[2,3,1]→[2,1,3]→[1,2,3]. It can be shown that achieving this in fewer than 33 moves is impossible.

Test case 33: PP can be made End Sorted using one operation, by swapping 11 and 22.

Test case 44: PP can be made End Sorted using one operation, by swapping 11 and 22.

For Solution

Click Here

Leave a Comment