KOI 어린이 집에는 N 명의 아이들이 있다. 오늘은 소풍을 가는 날이다. 선생님은 1 번 부터, N 번까지 번호가 적혀있는 번호표를 아이들의 가슴에 붙여 주었다. 선생님은 아이들을 효과적으로 보호하기 위해 목적지까지 번호순서대로 일렬로 서서 걸어가도록 하였다. 이동 도중에 보니 아이들의 번호순서가 바뀌었다.
그래서 선생님은 다시 번호 순서대로 줄을 세우기 위해서 아이들의 위치를 옮기려고 한다. 그리고 아이들이 혼란스럽지 않도록 하기 위해 위치를 옮기는 아이들의 수를 최소로 하려고 한다.
예를들어, 7 명의 아이들이 다음과 같은 순서대로 줄을 서 있다고 하자.
3 7 5 2 6 1 4아이들을 순서대로 줄을 세우기 위해, 먼저 4 번 아이를 7 번 아이의 뒤로 옮겨 보자. 그러면
3 7 4 5 2 6 1이제, 7 번 아이를 맨 뒤로 옮긴다.
3 4 5 2 6 1 7다음, 1 번 아이를 맨 앞으로 옮긴다.
1 3 4 5 2 6 7마지막으로 2 번 아이를 1 번 아이의 뒤로 옮기면 번호 순서대로 배치된다.
1 2 3 4 5 6 7위의 방법으로는 모두 4 명의 아이를 옮겨 번호 순서대로 줄을 세운다. 위의 예에서 3 명의 아이만을 옮겨서는 순서대로 배치할 수 없다. 따라서, 4 명을 옮기는 것이 가장 적은수의 아이를 옮기는 것이다.
N 명의 아이들이 임의의 순서로 줄을 서 있을 때, 번호 순서대로 배치하기 위해 옮겨지는 아이의 최소 수를 구하는 프로그램을 작성하시오.
입력 7 3 7 5 2 6 1 4 출력 4
출처: koi 중등 기출