Description

给定一个长度为n 的数列P，满足| Pi | ≤ 10^9

求有多少对（a，b，c，d），满足下列约束：

①1 ≤ a ≤ b < c ≤ d ≤ n

②b-a=d-c

③c-b-1 等于恰好等于给定的F，且F>0

④Pa+i=Pc+i 对于所有i（0≤i≤b-a）均成立

只要（a，b，c，d）中有任意一个参数不同，我们就认为是不同的

Format

Input

第一行两个正整数n，F

第二行n 个正整数Pi

N<=10^5

Output

一个整数，为符合条件的（a，b，c，d）的对数

Samples

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

6