Description

假如你现在拥有n名手下，你的每个手下都有一个不同的法力值a[i],现在他们整齐地排成一列，你要挑选其中的三个，使得中间那个人的法力值和位置都在另外两个人之间（意味着你的手下的位置是不能变动的），问你有多少种选择方法。

Input

第一行一个正整数个n（n>= 3 && n <= 20000），第二行n个正整数a[i]。

Output

输出共一行，即每组数据选择方法总数。

Sample 1

Input

8
19758 14190 11463 22304 1246 20856 5532 2310

Output

17

Limitation

20ms, 1024KiB for each test case.
(a[i] >= 1 && a[i] <= 100000).