#767. 【基础】机房排位

【基础】机房排位

说明

XX和小YY来到机房,发现机房门口排了一个长长的队伍。他们走近一看,原来这些人正在为练习中国国粹日本玩法而发愁……

机房门口排了n n 个人,第 ii 个人的身高为hi h_i 。他们想分成若干组一起学习。

每一组同学会坐在机房的同一列中。由于后面的同学可以看到前面严格矮于他的同学的屏幕,从而产生“不正当”行为。因此同一列的同学身高必须单调不增。

所有同学按照一开始排队的顺序依次进入机房。每位同学可以选择坐在之前某个同学后面,也可以选择坐在某个没有人的列的第一个位置。机房的行数和列数没有限制。

XX和小YY要帮助他们求出最少可以分多少组一起学习。

输入格式

第一行一个整数n n 表示总人数。

第二行 nn 个整数 h1h_1 h2h_2 ... hnh_n ,表示这些人的身高。

输出格式

一行一个整数,表示最少组数。

样例

7
6 3 6 1 2 4 5
4

提示

样例中一种可行的分组方案:第1、3、4个人分到第1组,第2、5个人分到第2组,第6个人分到第3组,第7个人分到第4组。这样一共分了4组。没有更优的方案。

数据范围

对于所有测试点,1n21050hi1091≤n≤2*10^5 ,0≤h_i≤10^9