#1804 정렬

24  5 s   128 MB  

Description

다음과 같은 방식의 숫자로 이뤄진 배열을 오름차순으로 정렬을 하려고 한다.

  1. 숫자를 하나 고르고 이를 제거한다.
  2. 고른 숫자를 배열 맨 앞에 위치시킨다.

위의 방식을 사용하여 정렬을 할 때 위의 방식의 횟수를 최소로 하는 프로그램을 작성하라.

예를 들어 (3,2,1)이 존재할 경우 우선 2를 골라 (2,3,1)을 만들고, 다음에 1을 골라 (1,2,3)을 만들면 총 2번 만에 정렬을 할 수 있다.

Input

입력의 첫 줄에는 배열에 존재하는 정수의 개수 N ( 1≤N≤300,000 )이 입력된다.

그 다음 N개의 줄에는 배열에 들어있는 N개의 숫자가 입력되며, 입력되는 순서와 배열의 초기 위치는 동일하다. 또한 입력되는 수의 범위는 1이상 N이하의 숫자이며, 각 숫자는 한번씩만 등장한다.

Output

입력에 대한 최소 횟수를 구하라.

Sample Input

Sample Output

3
3
2
1
2

Sample Input 2

4
1
3
4
2

Sample Output 2

2