题目描述

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

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

样例输入2

5
10 20 30 20 10

样例输出2

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分) : 无特殊限制。