问题 2119. -- 排队

2119: 排队

时间限制: 1 Sec  内存限制: 128 MB
提交: 55  解决: 25
[提交][状态][讨论版]

题目描述

n个人排成一条直线（一排），给出队伍中每个人的身高，每个人只能看到站在他右边且个头比他小没有被其他人挡住的人。请求出所有人可以看到的人数之和。

输入

第1行1个正整数N（1<=N<=80000)
下面的N行，每行给出一个正整数hi，表示第i个人的身高。1<=hi<=109

输出

一行一个数，表示所有人可以看到的人数之和

样例输入

6
10
3
7
4
12
2

样例输出

5

提示

样例解释：第一个人能看到第2、3、4三个人，第二个人看不到任何人，第三个人可以看到第4个人，第四个人看不到任何人，第五个人可以看到第6个人，第六个人看不到任何人。所以一共是3+0+1+0+1+0=5

来源

单调栈

[提交][状态]