#8982. 「第2次PTA认证」最萌身高差 普及/提高−

时间限制:1000 ms 内存限制:256 MiB 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Wind_Rises

题目描述

位同学获得了奖学金,现要从中选出两位代表上台领奖。出于“审美”要求,希望选出的两位代表 满足: 的身高比 高, 获得的奖

学金比 多,且奖学金的差额大于 。请计算选取上台同学的方案数。

输入格式

第一行包含两个正整数

第二行包含 个正整数 ,分别代表第 位同学获得的奖学金。输入顺序在前的同学身高较高。

输出格式

输出一个正整数,表示方案数

样例

样例输入

复制6 2
6 5 4 3 2 1

样例输出

数据范围与提示

的数据满足:

的数据满足:

的数据,可以考虑逐次使用冒泡排序+二分查找完成。

的数据,可以考虑采用归并排序的思路通过分治递归求解,也可以考虑使用线段树优化查找。