奶牛棒球

题目描述:

农夫约翰的 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 的距离。

数据范围:

3 ≤ N ≤ 1000 ,
奶牛所在的位置坐标范围 [ 0, 10⁸ ]。

样例输入:

5
3
1
10
7
4

样例输出:

4

提示:

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

时间限制: 1000ms
空间限制: 256MB

---

来源: USACO 2013 December Contest Bronze