셔플

카드를 섞는 가장 흔한 방법은 리플 셔플 또는 도브테일 셔플이라고 부른다. 덱을 두 뭉치로 나눈 다음, 두 뭉치를 서로 끼워 넣어 하나로 합친다. 덱은 어느 위치에서든 나눌 수 있고, 두 뭉치는 어떤 방식으로든 끼워 넣을 수 있다. 끼워 넣을 때 각 뭉치 안의 카드 순서는 그대로 유지된다.

예를 들어 서로 다른 카드 10장으로 이루어진 덱이 다음과 같다고 하자.

1 2 3 4 5 6 7 8 9 10

여섯 번째 카드 뒤에서 나누면 두 뭉치는 다음과 같다.

1 2 3 4 5 6
7 8 9 10

이 둘을 끼워 넣으면 예를 들어 다음 순서가 나온다.

1 2 7 3 8 9 4 5 10 6

한 번 더 섞어 보자. 세 번째 카드 뒤에서 나누면 두 뭉치는 다음과 같다.

1 2 7
3 8 9 4 5 10 6

다시 끼워 넣으면 예를 들어 다음 순서가 나온다.

3 8 1 9 4 5 2 7 10 6

이것은 두 번 섞은 뒤에 나올 수 있는 순서 하나다. 서로 다른 카드 $n$장이 $1, 2, 3, \dots, n$ 순서로 완벽하게 정렬된 상태에서 시작한다고 하자. 덱의 순서 하나가 주어졌을 때, 그 순서를 만들어 낼 수 있는 최소 셔플 횟수를 구하라.

입력은 테스트 케이스 하나로 이루어진다. 프로그램은 서로 다른 입력으로 여러 번 실행될 수 있다. 첫 줄에 덱의 카드 수를 나타내는 정수 $n$ ($1 \le n \le 10^6$)이 주어진다. 둘째 줄에는 덱의 순서를 나타내는 서로 다른 정수 $c$ ($1 \le c \le n$) $n$개가 공백 하나로 구분되어 주어진다. $c$ 값은 항상 $1$부터 $n$까지의 순열이다.

주어진 순서를 만들어 낼 수 있는 최소 셔플 횟수를 정수 하나로 한 줄에 출력한다. 공백은 출력하지 않는다.