책정리

동혁이는 캠프를 마치고 집에 돌아와 책꽂이를 정리하고 있다. 책은 한 줄로 길게 꽂혀 있으며, 각 책은 1번부터 N번까지의 번호로 구분된다. 현재 책들은 뒤죽박죽 섞여 있고, 동혁이는 이 책들을 왼쪽부터 오른쪽으로 1번, 2번, …, N번 순서가 되도록 다시 정리하려고 한다.

책을 정리하는 방법은 다음 한 가지뿐이다. 책 한 권을 뽑아서 원하는 다른 위치에 다시 꽂는다. 이때 나머지 책들의 상대적인 순서는 그대로 유지된다.

예를 들어 책이 다음과 같이 꽂혀 있다고 하자.

1 5 2 3 4

여기서 5번 책을 뽑아 가장 뒤에 다시 꽂으면

1 2 3 4 5

가 되어 1번부터 N번까지 순서대로 정리가 끝난다.

현재 책들이 꽂힌 순서가 주어질 때, 책 정리를 끝내기 위해 책을 옮겨야 하는 최소 횟수를 구하여라.

첫째 줄에 책의 개수 N (1 ≤ N ≤ 200,000)이 주어진다.

둘째 줄에는 현재 책들이 꽂힌 순서가 공백으로 구분되어 주어진다. 이 순서는 1번부터 N번까지의 번호가 각각 한 번씩 나타나는 순열이다.

동혁이가 책 정리를 끝내기 위해 책을 옮겨야 하는 최소 횟수를 첫째 줄에 출력한다.