最萌身高差

题目描述

有 $N$ 位同学获得了奖学金，现要从中选出两位代表上台领奖。出于“审美”要求，希望选出的两位代表 $A$ 和 $B$ 满足：$A$ 的身高比 $B$ 高，$A$ 获得的奖学金比 $B$ 多，且奖学金的差额大于 $M$。请计算选取上台同学的方案数。

输入格式

第一行包含两个正整数 $N$ 和 $M$；第二行包含 $N$ 个正整数 $S_i$，分别代表第 $i$ 位同学获得的奖学金。输入顺序在前的同学身高较高。

输出格式

输出一个非负整数，表示方案数。

样例 #1

输入 #1

6 2
6 5 4 3 2 1

输出 #1

6

数据范围

$30\%$ 的数据满足：$1 \le N \le 100$；$100\%$ 的数据满足：$1 \le N \le 100000$，$1 \le M \le 100000$，$1 \le S_i \le 100000$。

提示

对 $30\%$ 的数据，可以考虑逐次使用冒泡排序+二分查找完成。对 $100\%$ 的数据，可以考虑采用归并排序的思路通过分治递归求解，也可以考虑使用线段树或树状数组优化查找。