T419963 「YAC Round 2」Light 的有序排列

 > 无论在任何时代，所谓的规则都是由被视为神者所制定的。

Light 是一个拥有超高的智商、极强的逻辑思维能力、完美无缺的演技还有 ~~各种颜艺~~ 的人。有一天，Light 想了一个问题。具体问题如下。 有一个长度为 $n$ 的排列 $p$。（一个长度为 $n$ 的排列指的是一个满足 $1$ 到 $n$ 中的所有正整数恰好出现 $1$ 次的数组。例如，$[3, 1, 2, 4]$ 是一个长度为 $4$ 的排列，而 $[5, 1, 2, 5, 3]$ 不是一个排列。） 他可以对这个排列 $p$ 进行如下三种操作： - **切割**：将排列切割成若干个序列，每个序列至少含有一个元素。(可以不执行切割操作，即排列保持原样) - **翻转**：选择其中一些序列并将其翻转。 - **组合**：将这些序列重新组合拼接得到一个新的排列。 Light 他想知道如果把这个排列变得有序（升序或降序），**最少需要的切割次数**。 对于排列的切割操作，例如有一个排列为 $[1, 3, 4, 5, 2, 6]$，可以将其切割为 $[1, 3], [4], [5, 2, 6]$ 或者是 $[1], [3, 4, 5], [2], [6]$。当然也可以不切割，保持原样。 对于序列翻转的操作，例如有一个切割出来的序列为 $[5, 2, 6]$，进行翻转后就变为 $[6, 2, 5]$ 。 Light 很快就想出了很好的解法，现在他想考验一下同样智力超群的你。

输入一共两行。 第一行包含一个整数 $n$，表示排列 $p$ 的长度。 第二行包含 $n$ 个整数，$p_1, p_2, \ldots, p_n$。保证输入的 $p$ 一定是一个长度为 $n$ 的合法的排列。

输出一个整数，表示将排列 $p$ 变得有序(升序或降序)需要的 **最少切割的次数**。

对于所有测试数据，$1 \le n \le 10^6$