34701번 - 독서실 자리 바꾸기

문제

대전과학고등학교의 독서실에는 큰 원형 테이블이 있고, 그 주위에 일정한 간격으로 $N$개의 좌석이 배치되어 있다. $N$은 홀수이며, 각 좌석은 시계 방향으로 1ドル$번부터 $N$번까지 번호가 매겨져 있다. 예를 들어, $N=7$일 때 독서실의 모습을 그림으로 나타내면 다음과 같다.

모든 좌석에 각각 한 명의 학생이 배정되어 있었지만, 주기적인 좌석 교체 시즌이 찾아오면서 각 학생은 새롭게 배정된 좌석(목표 좌석)으로 이동하게 되었다.

다만, 좌석 이동은 자유롭게 이루어지지 않는다. 다음 규칙을 따르는 질서 있는 좌석 교체 작업이 필요하다.

1. 각 학생은 자신의 처음 좌석에서 목표 좌석까지 시계 방향 또는 반시계 방향 중 더 짧은 경로로만 이동한다. 이동 방향을 바꾸거나 목표 좌석에 도달하기 전 정지하는 경우는 없다.
2. 좌석 교체는 여러 개의 라운드로 나누어 수행된다. 모든 학생은 정확히 하나의 라운드에 배정되어야 하며, 각 라운드에서는 배정된 학생들만 좌석 이동을 진행한다. (처음 좌석과 목표 좌석이 같은 학생도 하나의 라운드에 배정되어야 한다.) 그 외의 학생들은 독서실 밖에 나가 있어 좌석 이동에 영향을 주지 않는다.
3. 하나의 라운드는 배정된 모든 학생이 목표 좌석에 도달할 때까지 진행된다. 목표 좌석에 도달하지 못한 모든 학생들은 동시에 한 칸씩 이동하며, 목표 좌석에 도달하면 이동을 멈추고 해당 좌석을 점유한 채 정지한다.
4. 한 라운드 내에서 두 학생이 같은 좌석에 위치할 수 없고, 서로 교차하여 이동할 수도 없다. 이는 이동 중인 학생과 정지한 학생 모두에 적용된다.

대전과학고등학교에서는 이러한 질서를 통해 학생들의 이동 동선이 복잡하게 얽히지 않도록 하고자 한다. 이때, 규칙을 준수하면서 모든 학생이 자신의 목표 좌석에 도달할 수 있도록 하기 위해 필요한 최소 라운드 수를 구해 보자.

입력

첫째 줄에 정수 $N$이 주어진다. $(3\leq N\leq 199,円 999;$ $N$은 홀수$)$

둘째 줄에 $N$개의 정수 $b_1,b_2,\cdots,b_N$이 공백으로 구분되어 주어진다. $b_i$는 처음 좌석이 $i$번 좌석이던 학생이 새롭게 배정받은 목표 좌석 번호이다. $(1\leq b_i\leq N;$ 모든 $i≠j$에 대해 $b_i≠b_j)$

출력

규칙을 준수하면서 모든 학생이 목표 좌석에 도달할 수 있도록 하기 위한 최소 라운드 수를 출력한다.

제한

노트