问题描述

你是DISCO公司内部旅游的导游，这次是在DISCO presents 发现频道编程竞赛2016决赛中担任导游。

在公司内部旅游中，有 $N$ 个房间需要导游，每个房间都被分配了从 $1$ 到 $N$ 的编号。建筑物的结构是环形的，你可以从第 $i(1≦i≦N-1)$ 个房间移动到第 $i+1$ 个房间。你也可以从第 $N$ 个房间移动到第 $1$ 个房间。这些通道是单向的，无法逆向移动。

当你在第 $i$ 个房间时，你可以选择参观该房间或者移动到相邻的房间。然而，因为参与者会对重复参观同一个房间感到厌倦，所以每个房间只能参观一次。基于你多年的公司内部旅游经验，你知道当参观第 $i$ 个房间时，你可以得到一个表示有趣程度的整数 $A_i$。

公司内部旅游需从第一个房间开始，参观完所有房间后回到第一个房间。为了让参与者享受公司内部旅游，你决定按照参观房间的有趣程度进行排序，并确保房间的顺序是宽松单调递增的。在这样的约束下进行公司内部旅游，你需要最少进行多少次周回呢？

这里，一个由 $n$ 项组成的数列 $a$ 满足 $a_1$ $≦$ $a_2$ $≦$ ... $≦$ $a_n$，我们称其为宽松单调递增列。而从第一个房间出发，逐个访问所有房间并回到第一个房间的行为称为一次周回。

---

输入

输入是从标准输入中按以下格式给出的。

$N$ $A_1$ $A_2$ … $A_N$

• 第 $1$ 行是房间数量 $N (2≦N≦10^{5})$。
• 第 $2$ 行是表示每个房间参观时有趣程度的整数 $A_i (1≦A_i≦10^{5})$，以空格分隔。

输出

请输出满足给定条件的最少周回次数，以 $1$ 行结束。末尾不要忘记换行。

部分得分

本问题设置了部分得分。

• 对于满足 $2≦N≦100$ 的数据集，如果给出正确答案，可获得 $20$ 分。
• 对于满足条件 $1≦A_i≦N$ 且 $i≠j$ 时 $A_i≠A_j$ 的数据集，如果给出正确答案，除了上述部分得分外还可获得额外的 $10$ 分。
• 对于不包含额外限制条件的数据集，如果给出正确答案，还可以额外获得 $70$ 分。

---

示例 1

5
1 4 3 2 5

示例 1 输出

3

• 可以按照以下顺序参观房间，以 $3$ 次周回完成公司内部旅游。注意，允许从第一个房间出发并立即参观第一个房间。请注意，旅行必须在参观完所有房间后回到第一个房间。
• 在第一次周回中，参观第一个房间和第四个房间。
• 在第二次周回中，参观第三个房间。
• 在第三次周回中，参观第二个房间和第五个房间。
• 这个示例满足上述部分得分的第一个条件和第二个条件。

---

示例 2

5
1 2 3 4 5

示例 2 输出

1

• 可以在第一次周回中参观所有房间。
• 这个示例满足上述部分得分的第一个条件和第二个条件。

---

示例 3

5
5 1 2 3 4

示例 3 输出

1

• 可以在最后参观第一个房间后结束旅行，这样就可以在一次周回内完成旅行。
• 这个示例满足上述部分得分的第一个条件和第二个条件。

---

示例 4

8
1 1 1 2 2 2 3 3

示例 4 输出

1

• 请注意，房间的有趣程度可能存在重复的情况。
• 这个示例满足上述部分得分的第一个条件，但不满足第二个条件。