Sorting a permutation P62723

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.