Minimum reversals of maximal decreasing subarrays needed to sort array

Question

The input is a length n array, containing distinct integers from 1 to n.

We will perform the following algorithm. There are no choices to be made in the algorithm: the only goal is counting the number of reversals this algorithm will perform.

Algorithm is like below:

While(array not sorted in ascending order) do:
    Find all the maximal contiguous subarrays which are in decreasing order,
    and reverse each of them (simultaneously).

We want to find the total number of times reverse will be called in the above algorithm, in an optimal way (i.e. as efficiently as possible, so direct simulation is probably too slow).

Example 1:

4,3,1,2 // 1 reversal: [4, 3, 1]
1,3,4,2 // 1 reversal: [4, 2]
1,3,2,4 // 1 reversal: [3, 2]
1,2,3,4

// Reverse is called 3 times in above example

Example 2:

5 3 4 2 1 ---> 2 reversals: [5, 3], [4, 2, 1]
3 5 1 2 4 ---> 1 reversal: [5, 1]
3 1 5 2 4 ---> 2 reversals: [3, 1], [5, 2]
1 3 2 5 4 ---> 2 reversals: [3, 2], [5, 4]
1 2 3 4 5 ---> sorted

Total of 7 reversals

Note that O(n^2) reversals may be necessary to sort a sequence in this way, so a direct simulation can take that many steps to run, but there may be a way to count them faster than O(n^2).

If n = 2k, then the sequence k+1, k+2, ... , 2k, 1, 2, 3, ..., k will require k^2 reversals:

Reversals to be performed are surrounded by brackets

5, 6, 7, [8, 1], 2, 3, 4         // 1 reversal

5, 6, [7, 1], [8, 2], 3, 4       // 2 reversals

5, [6, 1], [7, 2], [8, 3], 4     // 3 reversals

[5, 1], [6, 2], [7, 3], [8, 4]   // 4 reversals

1, [5, 2], [6, 3], [7, 4], 8     // 3 reversals

1, 2, [5, 3], [6, 4], 7, 8       // 2 reversals

1, 2, 3, [5, 4], 6, 7, 8         // 1 reversal

1, 2, 3, 4, 5, 6, 7, 8

Total of 16 = (8/2)^2 reversals.

Things which I tried:

1. Trying to convert it to recursion.
2. Using stack to solve it.
3. Read about inversion but not able to solve this.
4. Read on codeforces about the thread but was not relevant to this post.