题目描述

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

假定现在有 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

5
10 20 30 20 10 

4 

数据范围

【样例1说明】 (1,2)(2,3)(3,4)(1,3)可以互相看见。 【样例 2 说明】 尽管参观者3能够看见参观者 1，但是参观者1不能看见参观者 3。因此(1,3)不能互相看见。【数据范围与约定】 对于全部数据，有1≤N≤ 10^6，1≤身高≤ 10^6。 测试点 1~3(共 30 分):N ≤ 400。 测试点 4~8(共 50分):N≤ 4000。 测试点 9~10(共 20 分):无特殊限制。