E. 奶牛棒球

内存限制:256 MiB 时间限制:1000 ms 输入文件: nnbq.in 输出文件: nnbq.out
题目类型:传统 评测方式:文本比较

题目描述

农夫约翰的 N 头奶牛排成一排,每头奶牛都位于数轴中的不同位置上。

它们正在练习投掷棒球。

农夫约翰观看时,观察到一组三头牛 (X,Y,Z) 完成了两次成功的投掷。

牛 X 把球扔给她右边的牛 Y,然后牛 Y 把球扔给她右边的牛 Z。

约翰指出,第二次投掷的距离不少于第一次投掷的距离,也不超过第一次投掷的距离的两倍。

请计算共有多少组牛 (X,Y,Z) 可能是约翰所看到的。

输入格式

第一行包含整数 N。

接下来 N 行,每行描述一头牛的位置。

输出格式

输出奶牛三元组 (X,Y,Z) 的数量。

(X,Y,Z) 需满足,Y 在 X 的右边,Z 在 Y 的右边,并且从 Y 到 Z 的距离在 [XY,2XY] 之间,其中 XY 表示从 X 到 Y 的距离。

样例

输入样例:

5
3
1
10
7
4

输出样例:

4

样例解释

四个可能的奶牛三元组为:1−3−7,1−4−7,4−7−10,1−4−10。

数据范围与提示

3≤N≤2000 ,

奶牛所在的位置坐标范围 [ 0,10^8 ]。