Manual sorting
It's time to organize the books on the shelf. You have n books, each uniquely numbered from 1 to n. Your goal is to arrange them in ascending order based on their numbers. While quicksort and insertion sort are efficient for computers, they aren't practical for manual sorting.
Instead, you'll sort the books by placing the i-th book into the i-th position. How many such operations are required to sort the books successfully? Here are two examples of these operations:
1 3 4 5 2 => 1 2 3 4 5, achieved by inserting 2 into its correct position.
1 3 4 5 2 => 1 4 3 5 2, achieved by inserting 3 into its correct position.
Input
The first line of the input contains an integer n (1 ≤ n ≤ 20) — the number of books on the shelf.
The second line contains n distinct integers from 1 to n — representing the initial order of the books.
Output
Output a single integer — the minimum number of operations of the specified type needed to sort the books.