PID460 / 诺诺的队列
题目描述

诺诺表现、成绩双优,于是校长给她一笔money,让她去外地玩玩。由于本地没有飞机场,所以诺诺只能坐火车去咯。所以诺诺今天去火车站买票,却看到了N多人在火车站里啊,诺诺一阵头晕。机灵的她突然发现,有N个人在队伍里(和上文的N毫无关系- -||),人们等得很无聊,于是他们开始转来转去,想在队伍里寻找自己的熟人。队列中任意两个人A和B,如果他们是相邻或他们之间没有人比A或B高,那么他们是可以互相看得见的。

诺诺想计算出有多少对人可以互相看见,那么你能帮帮诺诺吗?

本题数据范围:

40%的测试数据:N≤10000;

80%的测试数据:N≤100000;

100%的测试数据:N≤500000。

输入格式

输入的第一行包含一个整数N (1≤N≤500 000), 表示队伍中共有N个人;

接下来的N行中,每行包含一个整数,表示人的高度,人的高度<10000。

输出格式

输出仅有一行,包含一个数S,表示队伍中共有S对人可以互相看见。

样例输入
样例输出
提交题目 Error [ 更改语言 ] Language
C C++ Pascal Python2
相关讨论
查看更多讨论
发布新讨论 讨论