Problem1023--巨人排队

1023: 巨人排队

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 2843  Solved: 659
[Submit] [Status] [Web Board] [Creator:]

Description

巨人国的小学生放假了,老师要给小朋友们排队了。可是这个老师有强迫症,一定要路队上的小朋友按照身高从高到矮排序(也就是排在前面的不能比后面的矮)。小朋友呢也很调皮,一旦老师给他排好队就不愿意动了。这个时候小朋友们一个一个的从教室里出来了,每个小朋友一出来老师就要给小朋友安排好位置。请问老师最少要给小朋友排几条路队呢?

Input

对于每组数据,第一行一个数n,表示小朋友总数量(1<=n<=100000)

第二行n个整数,表示小朋友身高,身高不超过30000

Output

对于每组数据,输出一个整数,表示最少的路队数

Sample Input

8
389 207 155 300 299 170 158 65

Sample Output

2

HINT

最少要排两条路队,其中一种方案是398-207-155-65 300-299-170-158