Sorting a permutation P62723


Statement
 

pdf   zip

thehtml

Consider a permutation of the numbers of 1 to n, for a certain given n. At every step, you can choose one i between 1 and n, and to turn the elements of the first i positions of the permutation. The aim is to leave the permutation sorted (in increasing or decreasing order).

Write a program that computes the minimal number of necessary steps to sort a given permutation.

Input

Input consists of a natural n > 0, followed by a permutation of the numbers from 1 to n.

Output

Your program must print the minimal number of necesary steps to sort the permutation, following the format of the instances.

Public test cases
  • Input

    6
    6 5 4 3 2 1
    

    Output

    0 steps are needed
    
  • Input

    5
    3 2 1 4 5
    

    Output

    1 steps are needed
    
  • Input

    9
    3 9 6 5 4 1 2 7 8
    

    Output

    6 steps are needed
    
  • Information
    Author
    Salvador Roura
    Language
    English
    Translator
    Carlos Molina
    Original language
    Catalan
    Other languages
    Catalan
    Official solutions
    C++
    User solutions