题目描述(ID:12290)
标题: 音乐会的等待
标签: 数据结构
详情:
N个人正在排队进入一个音乐会。人们等得很无聊,于是他们开始转来转去,想在队伍里寻找自己的熟人。队列中任意两个人A和B,如果他们是相邻或他们之间没有人比A或B高,那么他们是可以互相看得见的。
写一个程序计算出有多少对人可以互相看见。
输入格式:
输入的第一行包含一个整数N, 表示队伍中共有N个人。

接下来的N行中,每行包含一个整数,表示人的高度,以毫微米(等于10的-9次方米)为单位,每个人的高度都小于2^31毫微米。这些高度分别表示队伍中人的身高。
输出格式:
输出仅有一行,包含一个数S,表示队伍中共有S对人可以互相看见。
限制: 对于30%的数据,N<=100
对于60%的数据,N<=1000
对于80%的数据,S<=2000000
对于100%的数据,N<=1000000
样例:

输入

7
2
4
1
2
2
5
1

输出

10
登录并解答