Sort by Hand

Time Limit : 8 sec, Memory Limit : 65536 KB

Problem I: Sort by Hand

It's time to arrange the books on your bookshelf. There are n books in the shelf and each book has a unique number; you want to sort the books according to the numbers. You know that the quick sort and the merge sort are fast sorting methods, but it is too hard for you to simulate them by hand - they are efficient for computers, but not for humans. Thus, you decided to sort the books by inserting the book with the number i into the i-th position. How many insertions are required to complete this task?

Input

The first line of the input is n (1 ≤ n ≤ 20), which is the number of books. The second line contains n integers v1, ... , vn (1 ≤ vin), where vi indicates the number of the book at the i-th position before the sorting. All vi's are distinct.

Output

Print the minimum number of insertions in a line. If it is impossible for him to complete the sort, print "impossible" (without quotes).

Sample Input 1

3
1 2 3

Output for the Sample Input 1

0

Sample Input 2

3
2 1 3

Output for the Sample Input 2

1

Sample Input 3

3
3 2 1

Output for the Sample Input 3

2

Sample Input 4

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

Output for the Sample Input 4

14

Source: ACM-ICPC Japan Alumni Group Winter Camp , Day 2, Tokyo, Japan, 2009-02-22
http://acm-icpc.aitea.net/