줄 세우기

어린이 $N$명이 놀이터에 한 줄로 서 있다. 각 어린이는 $1$부터 $N$까지의 서로 다른 번호를 하나씩 달고 있다(즉, 번호들은 $1$부터 $N$까지의 순열이다). 선생님은 다음 연산만을 사용해 어린이들을 번호가 작은 쪽부터 큰 쪽으로, 즉 $1, 2, \dots, N$ 순서가 되도록 세우려고 한다.

연산: 줄에 서 있는 어린이 중 한 명을 골라 줄의 맨 앞 또는 맨 뒤로 보낸다.

한 어린이가 빠져나가 빈자리가 생기면, 그 뒤에 있던 어린이들이 한 칸씩 앞으로 당겨 와서 빈자리를 메운다.

예를 들어 $5$명의 어린이가 다음 순서로 서 있다고 하자.

5 2 4 1 3

이때 다음과 같이 세 번의 연산으로 번호 순서대로 세울 수 있다.

1. $1$번 어린이를 맨 앞으로 보낸다. (5 2 4 1 3 → 1 5 2 4 3)
2. $4$번 어린이를 맨 뒤로 보낸다. (1 5 2 4 3 → 1 5 2 3 4)
3. $5$번 어린이를 맨 뒤로 보낸다. (1 5 2 3 4 → 1 2 3 4 5)

두 번 이하의 연산으로는 이 배열을 정렬할 수 없으므로, 이 경우 최소 이동 횟수는 $3$이다.

처음 줄 서 있는 상태가 주어질 때, 위 연산으로 번호 순서대로 세우기 위해 맨 앞이나 맨 뒤로 보내야 하는 어린이 수의 최솟값을 구하여라.

입력은 두 줄로 이루어진다. 첫째 줄에는 어린이 수를 나타내는 정수 $N$이 주어진다. 둘째 줄에는 처음에 줄 서 있는 어린이들의 번호가 서 있는 순서대로 공백 하나로 구분되어 주어진다. $1 \le N \le 1{,}000{,}000$이며, 주어지는 번호는 $1$부터 $N$까지의 정수를 정확히 한 번씩 사용한 순열이다.

번호 순서대로 세우기 위해 맨 앞이나 맨 뒤로 보내야 하는 어린이 수의 최솟값을 한 줄에 출력한다.