CodeForces-251A: Points on Line

单调栈&单调队列

链接：CodeForces-251A

Description

Little Petya likes points a lot. Recently his mom has presented him n points lying on the line OX. Now Petya is wondering in how many ways he can choose three distinct points so that the distance between the two farthest of them doesn't exceed d.

Note that the order of the points inside the group of three chosen points doesn't matter.

Input

The first line contains two integers: n and d $(1 ≤ n ≤ 10^5; 1 ≤ d ≤ 10^9)$. The next line contains n integers $x_1, x_2, ..., x_n$, their absolute value doesn't exceed $10^9$ — the x-coordinates of the points that Petya has got.

It is guaranteed that the coordinates of the points in the input strictly increase.

Output

Print a single integer — the number of groups of three points, where the distance between two farthest points doesn't exceed d.

Please do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.

Example

Input
4 3
1 2 3 4
Output
4
Input
4 2
-3 -2 -1 0
Output
2
Input
5 19
1 10 20 30 50
Output
1

Note

In the first sample any group of three points meets our conditions.

In the seconds sample only 2 groups of three points meet our conditions: {-3, -2, -1} and {-2, -1, 0}.

In the third sample only one group does: {1, 10, 20}.

题意：输入n和d，按照升序输入n个数字，从n个数字中任意选出三个，使他们之间最大和最小值的差值不超过d,问有多少种选法。

分析：输入的数字已经是升序，因此一次压入队列当中，队首的数字一定是最小的，这个时候判断下一位即将入队的数字与队首数字的差值是否不超过d，如果不超过d，那么从队列中再从队列中已有的数字（cnt个）中任选2个即可，那么就要$C^2_{cnt}$种选法。可推出$C^2_n=1+2+3+……(n-1)$。

• 代码：

#include<stdio.h>
#include<iostream>
#include<queue>
#define LL long long
using namespace std;
int main()
{
    LL n,d;
    while(scanf("%lld%lld",&n,&d)!=EOF)
    {
        LL x,ans=0;
        LL cnt=0;
        queue<LL>q;
        while(n--)
        {
            scanf("%lld",&x);
            q.push(x);
            cnt++;
            while(x-q.front()>d)
            {
                q.pop();
                cnt--;
            }     
            if(x-q.front()<=d)
                ans+=(cnt-1)*(cnt-2)/2; 
        }
        cout<<ans<<endl;
    }
    return 0;
}