Problem Statement

Given is $a permutation p_1,\dots,p_n$ of $1,\dots,n$.
On this permutation, you can do the operations below any number of times in any order.

• Reverse the entire permutation. That is$, rearrange p_1,p_2,\dots,p_n$ to $p_n,p_{n-1},\dots,p_1$.
• Move the term at the beginning to the end. That is$, rearrange p_1,p_2,\dots,p_n$ to $p_2,\dots, p_n, p_1$.

Find the minimum number of operations needed to sort the permutation in ascending order.
In the given input, it is guaranteed that these operations can sort the permutation in ascending order.

Input

Input is given from Standard Input in the following format:
n
$p_1 \dots p_n$

Output

Print the minimum number of operations needed to sort the permutation in ascending order.

Constraints

• $2 \leq n \leq 10^5$
• $p_1,\dots,p_n$ is a permutation of $1,\dots,n$.
• The operations in Problem Statement can sort $p_1,\dots,p_n$ in ascending order.

Sample Input 1

3
1 3 2

Sample Output 1

2

You can sort it in ascending order in two operations as follows.

• Move the term at the beginning to the end: now you have 3, 2, 1.
• Reverse the whole permutation: now you have 1, 2, 3.

You cannot sort it in less than two operations, so the answer is 2.

Sample Input 2

2
2 1

Sample Output 2

1

Doing either operation once will sort it in ascending order.
You cannot sort it in less than one operation, so the answer is 1.

Sample Input 3

10
2 3 4 5 6 7 8 9 10 1

Sample Output 3

3

You can sort it in ascending order in three operations as follows.

• Reverse the whole permutation: now you have 1,10,9,8,7,6,5,4,3,2.
• Move the term at the beginning to the end: now you have 10,9,8,7,6,5,4,3,2,1.
• Reverse the whole permutation: now you have 1,2,3,4,5,6,7,8,9,10.

You cannot sort it in less than three operations, so the answer is 3.

Sample Input 4

12
1 2 3 4 5 6 7 8 9 10 11 12

Sample Output 4

0

No operation is needed.

见题面 Input 部分

见题面 Output 部分