손으로 정렬하기

면접 대비

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

요약

책 n권의 번호 순열이 주어질 때, 책 한 권씩 알맞은 위치에 끼워 넣어 정렬하는 최소 삽입 횟수를 구합니다.

난이도: 보통10점 중 4점
유형: 동적 계획법, 배열
정답자: 아직 제출이 없습니다

문제

책장에 있는 책을 정리할 때가 되었다. 책장에는 $n$ 권의 책이 있고, 각 책에는 서로 다른 번호가 붙어 있다. 책을 번호 순서대로 정렬하려고 한다. 퀵 정렬과 병합 정렬은 빠른 방법이지만 손으로 흉내 내기에는 너무 어렵다. 이 방법들은 사람보다 컴퓨터에 적합하다. 그래서 번호가 $i$ 인 책을 $i$ 번째 위치에 끼워 넣는 방식으로 정렬하기로 했다. 이 작업을 끝내는 데 필요한 삽입 횟수는 몇 번인가?

입력

첫째 줄에 책의 수 $n$ ( $1 \le n \le 20$ )이 주어진다. 둘째 줄에는 정렬하기 전 $i$ 번째 위치에 있는 책의 번호 $v_1, \ldots, v_n$ ( $1 \le v_i \le n$ )이 주어진다. 모든 $v_i$ 는 서로 다르다.

출력

최소 삽입 횟수를 한 줄에 출력한다. 정렬을 끝낼 수 없으면 "impossible"(따옴표 제외)을 출력한다.

예제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

예상 출력