C. 排列排序问题
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

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]$$$。

Input

第一行包含一个整数 $$$n\ (1\le n\le 10^6$$$)，表示排列 $$$p$$$ 的长度。

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

Output

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

Examples
Input
5
1 2 3 5 4
Output
1
Input
3
3 2 1
Output
0