题目描述

小明刚刚学会了数列的排序，现在他有一个长度为 $n$ 的排列 $p$ ，他认为 $p$ 必须是有序的，所以他打算将其进行排序。

他可以对这个排列进行如下操作：

• 将这个排列切割成若干个序列（也可以不切割，保持原样），每个序列至少含有一个元素；
• 选择其中一些序列并将它们翻转；
• 将这些序列按照他的意愿重新组合拼接得到一个新的排列。

小明觉得切割操作太累了，他想知道如果必须把这个排列变得有序，至少需要切割多少次。

• 一个长度为 $n$ 的排列的定义为，包含从 $1$ 到 $n$ 这 $n$ 个不同的整数的序列，每个整数恰好出现一次。
• 序列翻转的定义为，假设存在一个长度为 $m$ 的序列 $[a_1, a_2, ..., a_{m-1}, a_m]$，那么将这个序列翻转后将会得到 $[a_m, a_{m-1}, ..., a_2, a_1]$ 。

输入格式

第一行包含一个整数 $n$，表示排列 $p$ 的长度。

第二行包含 $n$ 个整数，其中第 $i$ 个整数定义为 $p_i$。保证输入的 $p$ 一定是长度为 $n$ 的排列。

输出格式

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

样例数据

5
1 2 3 5 4

1

3
3 2 1

0

大样例

P1550_3.in / P1550_3.out

数据范围

对于 $20\%$ 的数据，$1\le n \le 10$

对于 $50\%$ 的数据，$1\le n \le 100$

对于 $70\%$ 的数据，$1\le n \le 10000$

对于 $100\%$ 的数据，$1\le n \le 10^6$