342005 - CS 战队

通过次数

13

提交次数

21

Time Limit : 1 秒
Memory Limit : 128 MB

CS是一款非常流行的游戏。

为了提升战力,小凯组建了一支CS战队。评价这支战队的战力是这样的,设战队有n 个人,每个人的身高是a[i],战队中每有一个三人组(x,y,z)满足以下条件,即可提供1个战斗力。条件如下:

(1)a[x] < a[y] < a[z]

(2)a[y] - a[x] ≤ a[z] - a[y] ≤ 2 * (a[y] - a[x])

现在战队成员的身高千奇百怪,有lcm的,也有100km的。现在小凯迫切的想知道战队的战力,你能告诉他吗?

Input

第一行一个整数n,表示球队的人数;

接下来n行,每行一个数a[i],表示每个人的身高(1 ≤ a[i] ≤ 10^9)。

Output

一行一个数,表示CS战队的战斗力。

Examples

Input

5
3 
1
10
7
4

Output

4

Hint

样例解释:

1-3-7, 1-4-7, 4-7-10,和1-4-10

数据规模:

对于30%的数据,1 ≤ n ≤ 100;

对于50%的数据,1 ≤ n ≤ 500;

对于100%的数据,1 ≤ n≤1000。