#é. 【基础】机房排位

    Type: Default 1000ms 16MiB

【基础】机房排位

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.

说明

    小X和小Y来到机房,发现机房门口排了一个长长的队伍。他们走近一看,原来这些人正在为练习中国国粹日本玩法而发愁……
    机房门口排了 n 个人,第 i 个人的身高为 hi 。他们想分成若干组一起学习。
    每一组同学会坐在机房的同一列中。由于后面的同学可以看到前面严格矮于他的同学的屏幕,从而产生“不正当”行为。因此同一列的同学身高必须单调不增。
    所有同学按照一开始排队的顺序依次进入机房。每位同学可以选择坐在之前某个同学后面,也可以选择坐在某个没有人的列的第一个位置。机房的行数和列数没有限制。
    小X和小Y要帮助他们求出最少可以分多少组一起学习。

输入格式

第一行一个整数 n 表示总人数。
第二行 n 个整数 h1h2...hn ,表示这些人的身高。

输出格式

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

样例

7
6 3 6 1 2 4 5
4

提示

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


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

第七届SWPU-ACM老生预选赛

Not Attended
Status
Done
Rule
ACM/ICPC
Problem
187
Start at
2022-9-19 14:00
End at
2022-10-28 14:00
Duration
936 hour(s)
Host
Partic.
45