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