생일

오늘은 바이트만(Byteman)의 생일입니다. 생일 파티에는 바이트만을 포함해 $n$명의 아이들이 있으며, $1$번부터 $n$번까지 번호가 매겨져 있습니다. 부모님은 큰 원탁과 그 둘레에 놓인 $n$개의 의자를 준비했습니다.

아이들은 차례대로 앉습니다. $1$번 아이가 아무 자리에나 앉고, $2$번 아이는 그 왼쪽 자리에, $3$번 아이는 다시 그 왼쪽 자리에 앉는 식으로 이어집니다. 마지막으로 $n$번 아이가 $1$번과 $n-1$번 사이에 남은 자리에 앉습니다.

어떤 아이들은 특정한 아이와 너무 가까이 앉으면 시끄러워지기 때문에, 부모님은 순열 $p_1, p_2, \ldots, p_n$($1$부터 $n$까지의 서로 다른 정수)으로 주어지는 특정한 원형 순서로 아이들을 다시 앉히려고 합니다. 즉, $p_1$번 아이는 $p_n$번과 $p_2$번 사이에, $p_i$번 아이($i = 2, 3, \ldots, n-1$)는 $p_{i-1}$번과 $p_{i+1}$번 사이에, $p_n$번 아이는 $p_{n-1}$번과 $p_1$번 사이에 앉아야 합니다. $p_1$번 아이는 $p_n$번의 왼쪽에 앉을 수도 있고 오른쪽에 앉을 수도 있습니다. 즉 이 원형 순서는 두 회전 방향 중 어느 쪽으로도 실현될 수 있습니다.

원하는 순서를 만들기 위해 각 아이는 원탁을 따라 왼쪽 또는 오른쪽으로 몇 칸 이동합니다. 부모님은 아이마다 이동 방향과 거리(옮기는 자리 수)를 정합니다. 신호가 울리면 모든 아이가 동시에 일어나 새 자리로 이동해 앉습니다.

한 번의 재배치에서 혼란도(mess) 는 어떤 한 아이가 이동한 자리 수의 최댓값입니다. 원하는 원형 순서를 만드는 모든 재배치 중에서, 부모님은 혼란도가 가장 작은 방법을 찾고자 합니다.

$n$과 목표 순열을 읽어 가능한 최소 혼란도를 출력하는 프로그램을 작성하세요.

첫째 줄에 정수 $n$($1 \le n \le 10^6$)이 주어집니다.

둘째 줄에 아이들의 원하는 원형 순서를 나타내는 $n$개의 정수 $p_1, p_2, \ldots, p_n$이 공백 하나로 구분되어 주어집니다. 이 수들은 $\{1, 2, \ldots, n\}$의 순열입니다.

가능한 최소 혼란도를 정수 하나로 출력합니다.

$n = 6$이고 목표 순서가 $3\ 4\ 5\ 1\ 2\ 6$인 경우입니다. 왼쪽 그림은 처음 배치를 보여 줍니다. 한 가지 최적 재배치(가운데 그림)에서는 $1$번과 $2$번 아이가 한 칸, $3$번과 $5$번 아이가 두 칸 이동하고, $4$번과 $6$번 아이는 제자리에 있습니다. 이때 요구되는 순서가 성립합니다. $3$은 $6$과 $4$ 사이, $4$는 $3$과 $5$ 사이, $5$는 $4$와 $1$ 사이, $1$은 $5$와 $2$ 사이, $2$는 $1$과 $6$ 사이, $6$은 $2$와 $3$ 사이에 있습니다. 오른쪽 그림은 또 다른 최적 배치입니다. 두 경우 모두 어떤 아이도 두 칸을 넘게 이동하지 않으므로 최소 혼란도는 $2$입니다.