题目描述

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

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

输入格式

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

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

输出格式

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

输入数据 #1

4
175 160 180 165

输出数据 #1

4

解释 #1

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

输入数据 #2

5
10 20 30 20 10

输出数据 #2

4

解释 #2

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

数据范围

对于全部数据，有 $1 \leq N \leq 10^6$，$1 \leq$ 身高 $\leq 10^6$。

测试点

• 测试点 $1 \sim 3$（共 30 分）：$N \leq 400$。
• 测试点 $4 \sim 8$（共 50 分）：$N \leq 4000$。
• 测试点 $9 \sim 10$（共 20 分）：无特殊限制。