[Solution] Simply Strange Sort solution codeforces

Simply Strange Sort solution codeforces


You have a permutation: an array a=[a1,a2,,an]a=[a1,a2,…,an] of distinct integers from 11 to nn. The length of the permutation nn is odd.

Consider the following algorithm of sorting the permutation in increasing order.

A helper procedure of the algorithm, f(i)f(i), takes a single argument ii (1in11≤i≤n−1) and does the following. If ai>ai+1ai>ai+1, the values of aiai and ai+1ai+1 are exchanged. Otherwise, the permutation doesn’t change.

The algorithm consists of iterations, numbered with consecutive integers starting with 11. On the ii-th iteration, the algorithm does the following:

  • if ii is odd, call f(1),f(3),,f(n2)f(1),f(3),…,f(n−2);
  • if ii is even, call f(2),f(4),,f(n1)f(2),f(4),…,f(n−1).

It can be proven that after a finite number of iterations the permutation will be sorted in increasing order.

After how many iterations will this happen for the first time?

Input Simply Strange Sort solution codeforces

Each test contains multiple test cases. The first line contains the number of test cases tt (1t1001≤t≤100). Description of the test cases follows.

The first line of each test case contains a single integer nn (3n9993≤n≤999nn is odd) — the length of the permutation.

The second line contains nn distinct integers a1,a2,,ana1,a2,…,an (1ain1≤ai≤n) — the permutation itself.

It is guaranteed that the sum of nn over all test cases does not exceed 999999.

Output Simply Strange Sort solution codeforces

For each test case print the number of iterations after which the permutation will become sorted in increasing order for the first time.

If the given permutation is already sorted, print 00.

Example Simply Strange Sort solution codeforces
input

Copy
3
3
3 2 1
7
4 5 7 1 3 2 6
5
1 2 3 4 5
output

Copy
3
5
0
Note

In the first test case, the permutation will be changing as follows:

  • after the 11-st iteration: [2,3,1][2,3,1];
  • after the 22-nd iteration: [2,1,3][2,1,3];
  • after the 33-rd iteration: [1,2,3][1,2,3].

In the second test case, the permutation will be changing as follows:

  • after the 11-st iteration: [4,5,1,7,2,3,6][4,5,1,7,2,3,6];
  • after the 22-nd iteration: [4,1,5,2,7,3,6][4,1,5,2,7,3,6];
  • after the 33-rd iteration: [1,4,2,5,3,7,6][1,4,2,5,3,7,6];
  • after the 44-th iteration: [1,2,4,3,5,6,7][1,2,4,3,5,6,7];
  • after the 55-th iteration: [1,2,3,4,5,6,7][1,2,3,4,5,6,7].

In the third test case, the permutation is already sorted and the answer is 00.

Solution: Click here

Simply Strange Sort solution codeforcessolution codeforcescodeforces solutioncodeforces freshersonline

Leave a Comment