3次元あみだくじ

$N$ 本の垂直な棒が、正 $N$ 角形の各頂点に1本ずつ置かれている。上から見たとき、棒には時計回りに $1,2,\cdots,N$ の番号が付いている。

隣り合う2本の棒を結ぶ水平な横線を、任意の高さに追加できる。$1$ 番と $N$ 番の棒も隣り合っている。同じ2本の棒の間に横線を何本追加してもよく、複数の横線を同じ高さに置いてもよい。ただし、同じ高さの2本の横線が同じ棒につながっていてはならない。

ある棒の上端から下に進み、横線に出会うたびに、その横線を通って隣の棒に移り、再び下に進む。これを下端に到達するまで繰り返す。

長さ $N$ の順列 $A_1,A_2,\cdots,A_N$ が与えられる。 番の棒の上端から出発すると、 番の棒の下端に到達するように横線を配置したい。

必要な横線の本数の最小値を求めよ。

入力は次の形式で与えられる。

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

必要な横線の本数の最小値を1行に出力する。

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