You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目限制

1000 ms 128 M

题目描述

假设你有编号分别为1--n的n张卡片，现在小A先打乱这些卡片的顺序（类似于扑克牌的洗牌），也就是这些卡片不一定严格按照编号1--n的顺序排序了。

然后由小C将这些卡片恢复为按照编号1--n排序。而小C比较善于动脑筋，他想到可以将此次排序分成多个小任务来完成。具体就是将这些可能乱序的卡片分成若干份（此时不能打乱卡片的现有相对顺序），然后只需要对每一份进行排序就能实现将所有的n张卡片完成排序。

请问按照小C的排序方法，最多能将卡片分成多少份就能实现排序任务？

输入格式

第一行一个数n；

第二行n个数表示a[i] ，以空格隔开，存储每张卡片的编号。

n<=100000

输出格式

输出一个数，表示最多分成的份数。

数据范围

对于20%的数据，1≤n≤20；

对于53%的数据，1≤n≤1000；

对于60%的数据，1≤n≤2000；

对于100%的数据，1≤n≤100000。

输入样例

input1:

5

5 4 3 2 1

input2:

3

3 2 1

input3:

8

3 2 1 4 8 6 5 7

输出样例

output1：

1

output2 ：

1

output3:

3

样例1解释

将卷子分成2叠或者更多块，都无法得到所需的结果。

例如，分成 [5, 4], [3, 2, 1]，排序得到的结果是 [4, 5，,1, 2, 3] ，这不是有序的数组。

样例3解释：

将卡片分为[3 2 1] [4] [8 6 5 7]三份，然后分别排序，即可实现完整排序，多于3份都不可能实现最终的1 2 3 4 5 6 7 8