Sorting a permutation P77983


Statement
 

pdf   zip

thehtml

Given a permutation of {1, …, n}, you must sort it in increasing order. The only operation allowed is to reverse the first i elements of the current permutation, for any 2 ≤ in.

For instance, in one step we can transform [3, 5, 2, 4, 1] into [5, 3, 2, 4, 1], [2, 5, 3, 4, 1], [4, 2, 5, 3, 1] and [1, 4, 2, 5, 3].

Given a permutation, what is the minimum number of steps to sort it?

Input

Input consists of several permutations, each with an n between 1 and 18, followed by n different numbers between 1 and n.

Output

For every permutation, print the minimum number of operations to sort it.

Public test cases
  • Input

    3  1 2 3
    2  2 1
    1  1
    4  2 1 4 3
    6  1 3 2 6 5 4
    8  4 1 7 8 3 6 5 2
    18  11 17 3 10 14 1 18 5 9 6 13 15 4 8 2 12 16 7
    

    Output

    0
    1
    0
    3
    5
    7
    19
    
  • Information
    Author
    Josep Grané
    Language
    English
    Official solutions
    C++
    User solutions
    C++