4205: 诺诺的队列（nnqueue）

【题目描述】

火车站里排队的人多得让诺诺一阵头晕。机灵的她突然发现，有N个人在队伍里，人们等得很无聊，于是他们开始转来转去，想在队伍里寻找自己的熟人。队列中任意两个人A和B，如果他们是相邻或他们之间没有人比A或B高，那么他们是可以互相看得见的。

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

【输入格式】

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

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

【输出格式】

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

【输入样例】

7

2

4

1

2

2

5

1

【输出样例】

10

【数据范围】

40%的测试数据：N≤10000；

80%的测试数据：N≤100000；

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