P12848 [蓝桥杯 2025 国 A] 游戏

小蓝正在进行一个游戏。这个游戏有 $n$ 个槽位和 $n-1$ 个石块，初始时第 $n$ 个槽位是空的，其余每个槽位都有一个石块，对于两个相连的槽位 $u, v$，若 $u$ 是空的，那么小蓝可以将 $v$ 里的石块移到 $u$ 中。开始时，对于任意的 $1 \leq i < n$，第 $i$ 个槽位和第 $i+1$ 个槽位是相连的。游戏的最终目的是将每一个编号为 $i$ 的石块移动到编号为 $i$ 的槽位中。 小蓝在经过几次简单的尝试后发现，这个游戏并不一定有解，但好在他可以花费 1 的代价，任选两个槽位使它们相连。小蓝希望你帮他求出，至少要花费多少的代价，能够让这个游戏有解。

输入的第一行包含一个正整数 $n$。 第二行包含 $n-1$ 个正整数 $a_1, a_2, \cdots, a_{n-1}$，相邻整数之间使用一个空格分隔，分别表示初始第 $i$ 个槽位内石块的编号，保证 $a_i$ 各不相同。

输出一行包含一个整数表示答案。

**【样例说明】** 小蓝可以令槽位 1 和槽位 5 相连，然后将石块 4 移动到槽位 5，将石块 1 移动到槽位 1，将石块 2 移动到槽位 2，将石块 3 移动到槽位 3，将石块 4 移动到槽位 4，即可完成游戏的目标。 **【评测用例规模与约定】** 对于 30% 的评测用例，$n \leq 5$； 对于 50% 的评测用例，最小代价不超过 1； 对于所有评测用例，$1 \leq n \leq 3 \times 10^5$，$1 \leq a_i < n$。