Shuffles

The most common way to shuffle a deck of cards is called the riffle shuffle, or dovetail shuffle. The deck is split into two stacks, and the two stacks are then interleaved into one deck. The deck can be split anywhere, and the two stacks can be interleaved in any way. Interleaving keeps the order of the cards inside each stack.

For example, take a deck of 10 distinct cards.

1 2 3 4 5 6 7 8 9 10

Split it after the sixth card, which gives these two stacks.

1 2 3 4 5 6
7 8 9 10

Interleaving them can produce this order.

1 2 7 3 8 9 4 5 10 6

Shuffle once more. Splitting after the third card gives these two stacks.

1 2 7
3 8 9 4 5 10 6

Interleaving them again can produce this order.

3 8 1 9 4 5 2 7 10 6

That is one order the deck can reach after 2 shuffles. Suppose there are $n$ distinct cards and they start out perfectly ordered as $1, 2, 3, \dots, n$. Given one ordering of the deck, find the smallest number of shuffles that could produce that ordering.

Each input consists of a single test case. Your program may be run several times on different inputs. The first line holds one integer $n$ ($1 \le n \le 10^6$), the number of cards in the deck. The second line holds $n$ distinct integers $c$ ($1 \le c \le n$), separated by single spaces, giving an ordering of the $n$ cards. The values $c$ are always a permutation of the numbers $1$ through $n$.

Print one line with one integer, the minimum number of shuffles that could produce the given ordering. Print no spaces.