三维爬梯游戏

$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$ ().