描述

S国新研制了一种秘密武器,由排成一列的N个发射器构成,每个发射器有一个power 值Pi。武器发动攻击的方式很特殊,需要确定四个参数(a,b,c,d),其中a<=b<c<=d,且参数需要满足以下条件:
1、b-a=d-c。
2、c-b-1恰好等于给定阀值F(F>0)。
3、P[a+i]=P[c+i]对于所有的i (0<=i<=b-a)均成立。
我们说两种攻击方式不同,当且仅当四个参数中至少有一个参数不同。现在,你需要统计这套秘密武器一共有多少种不同的攻击方式。

输入格式

第一行两个正整数,N和F。
第二行N个正整数,表示发射器的power值Pi。

输出格式

一个整数,表示秘密武器可以发动多少种不同的攻击。

样例输入

11 4
1 1 1 4 1 -8 1 1 1 4 1

样例输出

6

数据范围与约定

  • 对于10%的数据,1<=N<=100。
  • 对于30%的数据,1<=N<=2500。
  • 对于60%的数据,1<=N<=10000。
  • 对于100%的数据,1<=N<=100000,1<=F<=N,-10^9<=Pi<=10^9。

来源

【Nescafé 31】杯NOIP模拟赛