题目描述

有 $n$ 个人排成一列等待进入音乐厅。等待期间，他们开始左顾右盼，试图在队列中找到认识的人。

对于队列中的两个人 $a$ 和 $b$，如果满足以下条件之一，他们就可以互相看见：

• 两人在队列中相邻；
• 两人之间所有人的身高都不超过 $a$ 和 $b$ 中较矮的那位。

请计算队列中共有多少对人可以互相看见。

输入格式

第一行包含一个整数 $n$，表示队列中共有 $n$ 个人。

接下来 $n$ 行，每行包含一个整数，表示队列中每个人的高度。

输出格式

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

样例

7 
2 
4 
1 
2 
2 
5 
1

10

提示

数据规模与约定

对于全部的测试点，保证 $1\le$ 每个人的身高 $\lt 2^{31}$，$1 \le n \le 5\times 10^5$。