Given an integer N, and a permutation, P of the integers from 1 to N, denoted as (a_1, a_2, ..., a_N), rearrange the elements of the permutation into increasing order, repeatedly making the following operation: Select a sub-portion of the permutation, (a_i, ..., a_j), and reverse its order.

Your goal is to compute the minimum number of such operations required to return the permutation to increasing order.

Example

If N = 3, and P = (3, 1, 2), we can do the following operations:

Select (1, 2) and reverse it: P = (3, 2, 1).

Select (3, 2, 1) and reverse it: P = (1, 2, 3).

output = 2

Very similar to the 969. Pancake Sorting but here we need to find the minimum number of such flips which is in my opinion much harder than the original Pancace Sorting problem. Any ideas? By intuition looks like a dynamic programming problem but I might be wrong here