### IOI '05 - Nowy Sacz, Poland

## Birthday

It is Byteman's birthday today. There are *n* children at his birthday
party (including Byteman). The children are numbered from 1 to *n*.
Byteman's parents have prepared a big round table and they have placed *n*
chairs around the table. When the children arrive, they take seats. The child
number 1 takes one of the seats. Then the child number 2 takes the seat on the
left. Then the child number 3 takes the next seat on the left, and so on.
Finally the child number *n* takes the last free seat, between the
children number 1 and *n*-1.

Byteman's parents know the children very well and they know that some of the
children will be noisy, if they sit too close to each other. Therefore the
parents are going to reseat the children in a specific order. Such an order can
be described by a permutation *p*_{1}, *p*_{2},
…,*p*_{n} (*p*_{1},
*p*_{2}, …, *p*_{n} are distinct
integers from 1 to *n*) - child *p*_{1} should sit between
*p*_{n} and *p*_{2}, child
*p*_{i} (for *i* = 2, 3, …, *n*-1) should
sit between *p*_{i-1} and *p*_{i+1},
and child *p*_{n} should sit between
*p*_{n-1} and *p*_{1}. Please note, that
child *p*_{1} can sit on the left or on the right from child
*p*_{n}.

To seat all the children in the given order, the parents must move each child around the table to the left or to the right some number of seats. For each child, they must decide how the child will move - that is, they must choose a direction of movement (left or right) and distance (number of seats). On the given signal, all the children stand up at once, move to the proper places and sit down.

The reseating procedure throws the birthday party into a mess. The mess is equal to the largest distance any child moves. The children can be reseated in many ways. The parents choose one with minimum mess. Help them to find such a way to reseat the children.

Your task is to write a program that:

- reads from the standard input the number of the children and the permutation describing the desired order of the children,
- determines the minimum possible mess,
- writes the result to the standard output.

### Input

The first line of standard input contains one integer*n*(1 ≤

*n*≤ 1 000 000). The second line contains

*n*integers

*p*

_{1},

*p*

_{2}, …,

*p*

_{n}, separated by single spaces. Numbers

*p*

_{1},

*p*

_{2}, …,

*p*

_{n}form a permutation of the set {1, 2, …,

*n*} describing the desired order of the children. Additionally, in 50% of the test cases,

*n*will not exceed 1000.

### Output

The first and the only line of standard output should contain one integer: the minimum possible mess.### Sample Input

6 3 4 5 1 2 6

### Sample Output

2

### Explanation

The left figure shows the initial arrangement of the children. The middle figure shows the result of the following reseating: children number 1 and 2 move one place, children number 3 and 5 move two places, and children number 4 and 6 do not change places. The conditions of arrangement are fulfilled, since 3 sits between 6 and 4, 4 sits between 3 and 5, 5 sits between 4 and 1, 1 sits between 5 and 2, 2 sits between 1 and 6, and 6 sits between 2 and 3. There exists another possible final arrangement of children, depicted in the right figure. In both cases no child moves more than two seats.
All Submissions

Best Solutions

**Point Value:** 20 (partial)

**Time Limit:** 2.00s

**Memory Limit:** 32M

**Added:** Jun 25, 2010

**Languages Allowed:**

C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

## Comments (Search)

Danielon Aug 28, 2009 - 12:56:59 pm UTC clarificationjargonon Aug 28, 2009 - 2:40:55 pm UTC Re: clarificationThis leads me to believe that each child may move 0 ≤ x < n seats exactly once.

bbi5291on Aug 28, 2009 - 3:44:54 pm UTC Re: clarification