[ Home | Task List | Submit ]

Gene Mutation

Time Limit: 1 second

Description

A 'supervirus' is now in an outbreak in the city! One of the most threatening characteristic of this 'supervirus' is that the infected person is asymptomatic during the first week of infection. However, after the incubation period, he will have skin rash over the whole body and die within 5 hours due to exaggerated immune response.

Another threatening feature of 'supervirus' is that the virus is very infectious. It can be transmitted by direct contact of the saliva of the infected person, so if he talks to someone, the virus is easily spreaded to that person.

Fortunately, Dr. Jones has invented a drug that can be injected to the infected people to cure them. Since the drug targets at the deoxyribonucleic acid (DNA in short) molecule inside the virus, the efficacy of the drug will be reduced if the 'supervirus' is mutated.

Dr. Jones discover that the gene of a 'supervirus' can be represented by a cycle of $N_$ distinct positive integers, and they are from $1$ to $N_$.
For example, when $N_$ = 5, the gene of the 'supervirus' is shown in figure 1.
Before mutation, exactly one of the $N_$ bonds in the gene must be broken down first. Then, it will mutate for several times by swapping several pairs of adjacent numbers, and then form the broken bond again. For example, after 2 mutations, the gene may become (see figure 2):

Dr. Jones cannot predict which bond will be broken, but he has confirmed that each 'supervirus' can break down one bond and form that bond again for at most once.

The current drug can be slightly modified to treat different mutated viruses, but it will have no therapeutic effect anymore when the gene becomes a cycle of $1, 2, ..., N$ in clockwise direction (see figure 3).

He calls this an 'ultravirus'.

In order to estimate the time left for inventing new drugs before the mutation of 'supervirus' into 'ultravirus', he asks you to find the minimum number of mutations needed.

Input

The first line is the integer $N_$.
The second line contains the number in the gene of the 'supervirus', arranged in clockwise direction.

Output

There is only $1$ line: the minimum number of mutations required for 'supervirus' to become 'ultravirus'.

Sample Input 1

5
1 2 4 5 3

Sample Output 1

2

Explanation for Sample I/O 1

First break down the bond between 1 and 3. After that, swap 5 and 3, and then 4 and 3, and form the broken bond again. (see Figure 4)

Sample Input 2

5
4 5 3 1 2

Sample Output 2

2

Explanation for Sample I/O 2

It is equivalent to the Sample 1 because the gene is cyclic.

Constraints

In test cases worth 30%, $1 \le N \le 8$.
In test cases worth 50%, $1 \le N \le 60$.
In test cases worth 70%, $1 \le N \le 300$.
In all test cases, $1 \le N \le 5000$. (Note that this is different from the question paper in the Final event, not 3000.)