순서 섞기

정수가 저장된 크기 $N$인 배열 $A$가 있을 때, ‘순서 섞기’ 연산은 아래와 같이 정의된다.

1. 크기가 $N$인 배열 $B$를 이용하여, 배열 $A$의 좌측 끝 또는 우측 끝에 있는 값 중 하나를 차례로 꺼내어 배열 $B$에 좌측부터 순서대로 저장한다. 아래의 그림에서 값이 꺼내지는 순서는 9, 34, 19, 12, 25, 4, 5, 36이다.

2. 배열 $B$를 배열 $A$에 복사한다.

위에서 보인 그림처럼 순서 섞기 연산을 하면 배열 $A$의 값은 다음과 같이 변경된다.

($34, 19, 5, 36, 4, 25, 12, 9) =$⇒ (9, 34, 19, 12, 25, 4, 5, 36)

배열 $A$의 $i$번째 원소를 Ai라고 나타내자. “$1 \le i$ < $j \le N$이면 Ai $\le Aj$이다.”가 성립할 때, “배열 $A$는 단조증가한다”라고 말한다.

정수가 저장된 크기 $N$인 배열 $A$가 주어질 때, 배열 $A$가 단조증가하도록 정렬하기 위해 필요한 ‘순서 섞기’ 연산의 최소 횟수를 계산하는 프로그램을 작성하시오.

• $1 \le N \le 300\,000$
• $1 \le Ai \le 109$

1. (4점) $N \le 8$.
2. (9점) 답이 2 이하.
3. (22점) Ai $\le 2$.
4. (18점) 모든 Ai가 서로 다름.
5. (47점) 추가 제약 조건 없음.

첫 번째 줄에 정수 $N$이 주어진다.

두 번째 줄에 배열 $A$에 저장된 $N$개의 정수 $A1$, ..., AN이 공백을 사이에 두고 차례대로 주어진다.

배열 $A$가 단조증가하도록 정렬하기 위해 필요한 ‘순서 섞기’ 연산의 최소 횟수를 출력한다.