该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

园博会吸引了很多参观者，为了保证参观质量，小明负责控制每个展区的人数，暂时无法入馆的参观者需要排队等候。小明为排队的参观者设计了一个小游戏，规则如下：

假定现在有 $N$ 位参观者排成一列，将他们从左往右编号为 $1$ 至 $N$。如果两位参观者 $i,j (i<j)$ 中间的每位参观者的身高都低于 $i,j$ 的身高，就认为 $i,j$ 可以互相看见。互相看到的两人可以获得一个徽章，请你编写程序帮小明计算：队列中有多少对参观者可以互相看见，便于小明发放徽章。

输入格式

输入的第 $1$ 行包含 $1$ 个整数 $N$，表示队列中的人数。

接下来 $1$ 行 $N$ 个整数，第 $i$ 个数表示参观者 $i$ 的身高。

输出格式

输出 $1$ 行 $1$ 个整数，表示答案。

样例

4
175 160 180 165

4

解释#1

$(1,2)\ (2,3)\ (3,4)\ (1,3)$ 可以互相看见。

5
10 20 30 20 10

4

解释#2

尽管参观者 $3$ 能够看见参观者 $1$，但是参观者 $1$ 不能看见参观者 $3$。因此 $(1,3)$ 不能互相看见。

数据范围

• 对于全部数据，有 $1 ≤ 𝑁 ≤ 10^6$，$1 ≤$ 身高 $≤ 10^6$。
• 测试点 $1\sim 3$（共 $30$ 分）：$𝑁 ≤ 400$。
• 测试点 $4\sim 8$（共 $50$ 分）：$𝑁 ≤ 4000$。
• 测试点 $9\sim 10$（共 $20$ 分）：无特殊限制。