[HUSTFC 2023] 排列排序问题

题目描述

JokerShaco 有一个长度为 $n$ 的排列 $p$,他认为一个排列必须是有序的,所以他打算将其进行排序。 他可以对这个排列进行如下操作: - 将这个排列切割成若干个序列(也可以不切割,保持原样),每个序列至少含有一个元素; - 选择其中一些序列并将它们翻转; - 将这些序列按照他的意愿重新组合拼接得到一个新的排列。 JokerShaco 认为切割操作非常累,他想知道如果必须把这个排列变得有序,至少需要切割多少次。 一个长度为 $n$ 的排列的定义为,包含从 $1$ 到 $n$ 这 $n$ 个不同的整数的序列,每个整数恰好出现一次。 序列翻转的定义为,假设存在一个长度为 $m$ 的序列 $[a_1,a_2,\dots,a_{m-1},a_m]$,那么将这个序列翻转后将会得到 $[a_m,a_{m-1},\dots,a_2,a_1]$。

输入输出格式

输入格式


第一行包含一个整数 $n\ (1\le n\le 10^6$),表示排列 $p$ 的长度。 第二行包含 $n$ 个整数,其中第 $i$ 个整数定义为 $p_i$。保证输入的 $p$ 一定是长度为 $n$ 的排列。

输出格式


输出一个整数,表示将排列 $p$ 变得有序所需的最少切割次数。

输入输出样例

输入样例 #1

5
1 2 3 5 4

输出样例 #1

1

输入样例 #2

3
3 2 1

输出样例 #2

0