문제
다음과 같은 방식의 숫자로 이뤄진 배열을 오름차순으로 정렬을 하려고 한다.
1. 숫자를 하나 고르고 이를 제거한다.
2. 고른 숫자를 배열 맨 앞에 위치시킨다.
위의 방식을 사용하여 정렬을 할 때 위의 방식의 횟수를 최소로 하는 프로그램을 작성하라.
예를 들어 (3,2,1)이 존재할 경우 우선 2를 골라 (2,3,1)을 만들고, 다음에 1을 골라 (1,2,3)을 만들면 총 2번 만에 정렬을 할 수 있다.
입력
입력의 첫 줄에는 배열에 존재하는 정수의 개수 N ( 1≤N≤300,000 )이 입력된다.
그 다음 N개의 줄에는 배열에 들어있는 N개의 숫자가 입력되며, 입력되는 순서와 배열의 초기 위치는 동일하다. 또한 입력되는 수의 범위는 1이상 N이하의 숫자이며, 각 숫자는 한번씩만 등장한다.
출력
입력에 대한 최소 횟수를 구하라.
예제 #1
3
3
2
1
2
예제 #2
4
1
3
4
2
2
출처
COCI 2010/2011 contest2 4
로그인해야 코드를 작성할 수 있어요.