墨墨的妈妈热爱炒股，她要求墨墨为她编写一个软件，预测某只股票未来的走势。股票折线图是研究股票的必备工具，它通过一张时间与股票的价位的函数图像清晰地展示了股票的走势情况。经过长时间的观测，墨墨发现很多股票都有如下的规律：之前的走势很可能在短时间内重现！如图可以看到这只股票A部分的股价和C部分的股价的走势如出一辙。通过这个观测，墨墨认为他可能找到了一个预测股票未来走势的方法。进一步的研究可是难住了墨墨，他本想试图统计B部分的长度与发生这种情况的概率关系，不过由于数据量过于庞大，依赖人脑的力量难以完成，于是墨墨找到了善于编程的你，请你帮他找一找给定重现的间隔（B部分的长度），有多少个时间段满足首尾部分的走势完全相同呢？当然，首尾部分的长度不能为零。

输入的第一行包含两个整数N、M，分别表示需要统计的总时间以及重现的间隔（B部分的长度）。接下来N行，每行一个整数，代表每一个时间点的股价。

输出一个整数，表示满足条件的时间段的个数

对于100%的数据，4≤N≤50000 1≤M≤10 M≤N 所有出现的整数均不超过32位含符号整数。

#include<cstdio>
#include<cstring>
#include<algorithm>

typedef long long ll;
const int len(50000);
ll a[len+10],d[len+10],ans;
int n,B,id[len+10];
struct AXLE
{
    ll a[len+10];int up;
    void deal()
    {
        for(int i=1;i<=n;i++)a[++up]=d[i];
        std::sort(a+1,a+1+up);
        int _up=1;
        for(int i=2;i<=up;i++)if(a[i]!=a[i-1])a[++_up]=a[i];
        up=_up;
    }
    int two(ll x)
    {
        int ans=up;
        for(int l=1,r=up,mid;l<=r;)
        if(a[mid=(l+r)>>1]<=x)l=mid+1,ans=mid;else r=mid-1;
        return ans;
    }
}axle;

int cnt[len+10],tmp[len+10],p[len+10],f[17][len+10],logg[len+10];
void swap(int &x,int &y){x^=y;y^=x;x^=y;}
int min(int a,int b){return a>b?b:a;}
int max(int a,int b){return a<b?b:a;}
void Fdeal()
{
    logg[0]=-1;
    for(int i=1;i<=n;i++)logg[i]=logg[i>>1]+1,f[0][i]=i+1;
    for(int j=1;j<=logg[n];j++)
    for(int i=1;i<=n;i++)f[j][i]=f[j-1][ f[j-1][i] ];
}
struct SA
{
    int str[len+10],now,limt;
    int sfa[len+10],rank[len+10],height[len+10];
    void put(int ty)
    {
        if(ty)for(int i=1;i<=n;i++)str[i]=d[i];
        else for(int i=1;i<=n;i++)str[i]=d[n-i+1]; 
        now=n;limt=axle.up;
//        fprintf(stderr,"now=%d\n",now);
    }
    bool cmp(int x,int y,int l){return x+l<=now&&y+l<=now&&rank[x]==rank[y]&&rank[x+l]==rank[y+l];}
    void doubling()
    {
//        fprintf(stderr,"doubling\n");
//        fprintf(stderr,"now=%d\n",now);
        for(int i=1;i<=now;i++)rank[i]=str[i],sfa[i]=i;
        for(int l=0,pos=0,sigma=limt;pos<now;sigma=pos)
        {
            pos=0;
            for(int i=now-l+1;i<=now;i++)p[++pos]=i;
            for(int i=1;i<=now;i++)if(sfa[i]>l)p[++pos]=sfa[i]-l;
            memset(cnt,0,sizeof(int)*(sigma+1)); pos=0;
            for(int i=1;i<=now;i++)cnt[rank[i]]++;
            for(int i=1;i<=sigma;i++)cnt[i]+=cnt[i-1];
            for(int i=now;i>=1;i--)sfa[cnt[rank[p[i]]]--]=p[i];
            for(int i=1;i<=now;i++)tmp[sfa[i]]=cmp(sfa[i],sfa[i-1],l)?pos:++pos;
            for(int i=1;i<=now;i++)rank[i]=tmp[i];
            l=!l?1:l<<1;
        }
        for(int i=1;i<=now;i++)rank[sfa[i]]=i;
        for(int i=1,j,k;i<=now;i++)
        {
            k=sfa[rank[i]-1]; if(!k)continue;
            j=height[rank[i-1]];    if(j)j--;
            while(str[i+j]==str[k+j])
                j++;
            height[rank[i]]=j;
        }
//        fprintf(stderr,"now=%d\n",now);
//        for(int i=1;i<=now;i++)
//        fprintf(stderr,"h=%d\n",height[i]);
    }
    int g[17][len+10];
    //lcp(x,y)=min[x,y-1]
    void Gdeal()
    {
        for(int i=1;i<=now;i++)g[0][i]=height[i+1];
        for(int j=1;j<=logg[now];j++)
        for(int i=1;i<=now;i++) g[j][i]=min(g[j-1][i],g[j-1][ f[j-1][i] ]);
    }
    int lcp(int x,int y)
    {
//        fprintf(stderr,"1:x= %d y=%d\n",x,y);
        x=rank[x];y=rank[y];
        if(x>y)swap(x,y); y--;
//        fprintf(stderr,"2:x= %d y=%d\n",x,y);
//        for(int i=x+1;i<=y;i++)
//        fprintf(stderr,"3:h=%d\n",height[i]);
        int k=logg[y-x+1];
        int w=1<<k;
        return min(g[k][x],g[k][y-w+1]);
    }
    void build(int ty)
    {
        put(ty); doubling(); Gdeal();
    }
}pre,suc;
int main()
{
    scanf("%d %d",&n,&B);
    for(int i=1;i<=n;i++)scanf("%lld",a+i),d[i-1]=a[i]-a[i-1];    
    n--;axle.deal();
//    fprintf(stderr,"n=%d B=%d\n",n,B);
    for(int i=1;i<=n;i++)d[i]=axle.two(d[i]);
    Fdeal(); pre.build(0); suc.build(1);
    for(int l=1,LL,RR;l+l+B<=n;l++)
        for(int i=l,x,y;i+l+B-1<=n;i+=l)
        {
//            fprintf(stderr,"x= %d y= %d\n",i,i+l+B);
            x=i; y=i+l+B;
            LL=pre.lcp(n-y+1,n-x+1); RR=suc.lcp(x,y);
//            fprintf(stderr,"LL= %d RR= %d l=%d\n",LL,RR,l);
            ans+=max(0,min(LL,l)+min(RR,l)-l);
//            fprintf(stderr,"ans=%lld\n",ans);
        }
    printf("%lld",ans);
    return 0;
}