该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Problem K. 你说的对，但是不给你吃

题目背景

在一个古老的帝国中，皇帝为了确保所有人民都得到适合自己身份的食物，设立了一个特别的分配系统。在这个系统中，食物被分为不同的等级，每个等级代表着不同的社会阶层。皇帝希望每个人都能获得与他们身份相匹配的食物，以维持帝国的和谐与秩序。

题目描述

作为帝国的首席分配官，zms 面临着一个复杂的挑战。有一系列的食物，每种食物被分配了一个等级，代表着它适合的社会阶层。这些食物等级构成了一个长度为 $n$ 的排列 $p$，包含从 $1$ 到 $n$ 的 $n$ 个不同等级，每个等级恰好出现一次。zms 的任务是通过一系列操作，将这些食物按等级从低到高顺序重新分配给不同阶层的人。

zms 可以依次进行以下操作：

1. Divide：将这个食物等级排列分割 $k$ 次，使得其变为 $k + 1$ 个子序列（每个子序列至少包含一个食物等级，也可以选择不分，保持原排列）；
2. Reverse：选择其中一些食物等级子序列，并将它们倒转（即将子序列中的食物等级顺序颠倒）；
3. Combine：将这些食物等级子序列按照你的意愿重新组合拼接，形成一个新的排列。

请你帮助 zms 找出在第一步（Divide）最少需要分割多少次，才能通过上述操作将原排列变为按等级从低到高的有序状态。

输入格式

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

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

输出格式

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

样例数据 #1

5
1 2 3 5 4

1

样例数据 #2

3
3 2 1

0

数据范围与约定

$1\le n\le 10^6, \ 1 \le p_i \le n$ 。保证每个 $p_i$ 恰好出现一次。

注意

• 分割的子序列是 连续 的。
• 操作必须依次进行，即先使用若干 Divide，再使用若干 Reverse，再使用若干 Combine。
• 若希望使用 Divide 将序列拆分为 $k + 1$ 个子序列，则必须使用 $k$ 次 Divide 操作。

在样例 1 中，以下是一种可行方法：

• 使用 1 次 Divide，拆分为 [1 2 3]，[5 4]
• 接下来使用 Reverse，将第二个子序列翻转为 [1 2 3], [4 5]
• 接下来使用 Combine，将子序列拼接为 [1 2 3 4 5]。
• 因此，需要进行的 Divide 的最少次数是 1。