P5846 [IOI 2005] bir

Today is Byteman’s birthday. There are $n$ children at his birthday party (including Byteman). The children are numbered from $1$ to $n$. Byteman’s parents prepared a big round table and placed $n$ chairs around it. When the children arrive, they sit down as follows: child $1$ sits on some chair, then child $2$ sits to the left of child $1$, then child $3$ sits to the left of child $2$, and so on. Finally, child $n$ sits on the last empty chair, i.e. between child $n-1$ and child $1$. Byteman’s parents know the children very well, and they know that if some children sit next to each other, they will be very noisy. Therefore, they will rearrange the children’s seats in a specific order. This order is given by a permutation $p_1,p_2,\cdots,p_n$ ($p_1,p_2,\cdots,p_n$ are integers from $1$ to $n$). Child $p_1$ will sit between $p_2$ and $p_n$, child $p_i$ ($i = 2,3,\ldots,n-1$) will sit between children $p_{i-1}$ and $p_{i+1}$, and child $p_n$ will sit between children $p_{n-1}$ and $p_1$. Note that $p_1$ may sit either to the left of $p_n$ or to the right of $p_n$. To make all children sit in the given order, Byteman’s parents must let each child move some seats to the left or to the right around the table. They must decide how each child moves, that is, they must decide a direction and a distance. For a given moving instruction, all children stand up at once and move to their target seats and sit down. This process makes the party messy. The messiness is defined as the maximum moving distance among all children. Since the children can move in many different ways, Byteman’s parents will choose the one that minimizes the messiness. Help them find such a plan. Your task is to write a program that reads from standard input the number of children and the permutation describing the target order, and computes the minimum possible messiness.

The first line contains an integer $n$ ($1 \le n \le 10^6$). The second line contains $n$ integers $p_1,p_2,\cdots,p_n$, separated by single spaces. $p_1,p_2,\cdots,p_n$ is a permutation of the set $\{1,2,\cdots,n\}$, describing the target order.

One line containing one integer: the minimum messiness.

For $50\%$ of the testdata, $1 \le n \le 1000$. For $100\%$ of the testdata, $1 \le n \le 10^6$. Translated by ChatGPT 5