3270. 看试卷

【题目描述】

在一次考试之后，作为班主任的T老师需要给n个学生改卷子，T老师有个习惯，就是按学号的先后来看卷子，所以T老师每次看卷子之前都需要给卷子排好先后次序再改。

但是因为T老师的空闲时间很短，所以他想尽量把这个排序的任务分成多次来做。因此他请你将卷子分成一小叠一小叠的（但不打乱卷子现有顺序），使得她只需要对每一叠分别排序，就能将整堆卷子排序。

初始的卷子次序为a[i],请问你最多能把卷子分成多少小叠。

保证卷子上面的学号为0...n-1的一个排列。

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

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

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

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

【输入格式】

第一行一个数n； 第二行n个数表示a[i]，以空格隔开。 n<=100000

【输出格式】

输出一个数，表示最多分出多少叠卷子。

【样例输入】

input example1: 
5 
4 3 2 1 0 
input example2: 
3 
2 1 0 
input example3: 
8 
2 1 0 3 7 5 4 6 

【样例输出】

output example1: 1 
output example2: 1 
output example3: 3 

【提示】

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

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

【来源】