Birthday

It is Byteman's birthday today. There are $n$ children at his birthday party (Byteman included), numbered from $1$ to $n$. Byteman's parents have prepared a big round table with $n$ chairs around it.

The children sit down in order. Child $1$ takes any seat. Child $2$ takes the seat to the left, child $3$ the next seat to the left, and so on, until child $n$ takes the last free seat, between child $1$ and child $n-1$.

Some children get noisy when they sit too close to certain others, so the parents want to reseat everyone into a specific cyclic order given by a permutation $p_1, p_2, \ldots, p_n$ (distinct integers from $1$ to $n$): child $p_1$ must sit between $p_n$ and $p_2$, child $p_i$ (for $i = 2, 3, \ldots, n-1$) must sit between $p_{i-1}$ and $p_{i+1}$, and child $p_n$ must sit between $p_{n-1}$ and $p_1$. Note that child $p_1$ may end up on either side of child $p_n$: the cyclic order can be realized in either rotational direction.

To reach the desired order, every child moves around the table some number of seats, either to the left or to the right; the parents choose a direction and a distance for each child. On a signal, all children stand up at once, walk to their new places, and sit down.

The mess of a reseating is the largest number of seats moved by any single child. Among all reseatings that produce the desired cyclic order, the parents want one with the smallest possible mess.

Write a program that reads $n$ and the target permutation and prints the minimum possible mess.

The first line contains one integer $n$ ($1 \le n \le 10^6$).

The second line contains $n$ integers $p_1, p_2, \ldots, p_n$ separated by single spaces, forming a permutation of $\{1, 2, \ldots, n\}$ that describes the desired cyclic order of the children.

Print a single integer: the minimum possible mess.

For $n = 6$ and the target order $3\ 4\ 5\ 1\ 2\ 6$, the left figure shows the initial seating. In one optimal reseating (middle figure), children $1$ and $2$ move one seat, children $3$ and $5$ move two seats, and children $4$ and $6$ stay put. The required order then holds: $3$ sits between $6$ and $4$, $4$ between $3$ and $5$, $5$ between $4$ and $1$, $1$ between $5$ and $2$, $2$ between $1$ and $6$, and $6$ between $2$ and $3$. Another optimal seating is shown on the right. In both, no child moves more than two seats, so the minimum mess is $2$.