Sort by Hand

시간 제한8초메모리 제한512 MB

요약

책 n권의 순열이 주어질 때, 번호 i인 책을 i번 위치로 옮기는 작업을 반복해서 정렬하는 데 필요한 최소 이동 횟수를 구한다.

난이도: 보통10점 중 4점
유형: 정렬, 구현, 완전 탐색
정답자: 아직 제출이 없습니다

문제

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?

입력

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 ≤ vi ≤ n), where vi indicates the number of the book at the i-th position before the sorting. All vi's are distinct.

출력

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

예제4

예제 1
입력
```
3
1 2 3
```
예상 출력
```
0
```
예제 2
입력
```
3
2 1 3
```
예상 출력
```
1
```
예제 3
입력
```
3
3 2 1
```
예상 출력
```
2
```

예제 4

입력

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

예상 출력