최적의 공정 셔플

공정 셔플(Fair shuffle)은 왼쪽에서 오른쪽으로 가로로 놓인 $N$장의 서로 다른 카드를 섞는 방법이다. 공정 셔플에서는 카드를 두 개의 연속된 구간으로 나눈다. 두 구간의 카드 수는 다를 수 있고, 한쪽 구간에는 카드가 0장일 수도 있다. 왼쪽 구간을 L, 오른쪽 구간을 R이라고 하자.

그다음 L의 카드와 R의 카드를 합치되, 각 구간 안에서의 카드 순서는 그대로 유지한다.

예를 들어 1 2 3 4 5를 L: 1 2와 R: 3 4 5로 나눈다고 하자. 카드는 여러 방식으로 합쳐질 수 있다.

• 1 3 2 4 5
• 1 3 4 2 5
• 3 4 5 1 2
• 1 2 3 4 5
• 그 밖의 방식

1 3 2 5 4는 가능한 결과가 아니다. R에 있는 카드 4와 5의 상대적 순서가 유지되지 않기 때문이다.

첫 번째 공정 셔플의 결과가 1 3 2 4 5라고 하자. 두 번째 공정 셔플에서는 L: 1 3 2 4와 R: 5로 나눈 뒤 1 3 2 5 4로 합칠 수 있다.

초기 수열 1 2 ... $N$에 $K$번의 공정 셔플을 적용한 최종 순열이 주어진다. $K$의 최솟값을 구하라.

첫 번째 줄에 덱에 있는 카드의 수 $N$ ($1 \le N \le 10^6$)이 주어진다. 두 번째 줄에는 카드의 최종 배열을 나타내는 1부터 $N$까지 정수의 순열이 주어진다.

초기 수열을 주어진 배열로 바꾸는 데 필요한 공정 셔플의 최소 횟수 $K$를 한 줄에 출력한다.