3차원 사다리타기

$N$개의 세로 막대기가 정$N$각형의 꼭짓점에 하나씩 수직으로 놓여 있다. 위에서 내려다보았을 때 막대기에는 시계 방향으로 $1,2,\cdots,N$의 번호가 붙어 있다.

서로 인접한 두 막대기를 잇는 수평 가로선을 원하는 높이에 추가할 수 있다. $1$번 막대기와 $N$번 막대기도 인접한다. 같은 두 막대기 사이에 여러 가로선을 추가해도 되며, 서로 다른 가로선이 같은 높이에 있어도 된다. 단, 같은 높이에 있는 두 가로선은 하나의 막대기를 공유하지 않아야 한다.

각 막대기의 맨 위에서 출발해 아래로 이동한다. 가로선을 만나면 가로선을 따라 연결된 막대기로 이동한 뒤 다시 아래로 이동한다. 이 과정을 맨 아래에 도착할 때까지 반복한다.

길이 $N$의 순열 $A_1,A_2,\cdots,A_N$이 주어진다. 번 막대기에서 출발하면 번 막대기의 맨 아래에 도착하도록 가로선을 배치하려고 한다.

필요한 가로선 개수의 최솟값을 구하여라.

입력은 다음과 같은 형식으로 주어진다.

$N$ $A_1\ A_2\ \cdots\ A_N$

첫째 줄에 필요한 가로선 개수의 최솟값을 출력한다.

• $3 \leq N \leq 1000$.
• $1 \leq A_i \leq N$ ().