정수가 저장된 크기 $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$번째 원소를 $A_i$라고 나타내자. “$1\le i<j\le N$이면 $A_i\le A_j$이다.”가 성립할 때, “배열 $A$는 단조증가한다”라고 말한다.

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

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

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

• $1\le N\le 300000$ 
• $1\le A_i\le {10}^9$ 

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