本题为虾仁的珠宝差异困难版本，两题的唯一区别在于本题的数据范围更大。

虾仁穿越到了大明朝洪武时期，当时正爆发胡惟庸案，身为锦衣卫一员的虾仁接收到洪武大帝的旨意要将胡惟庸党羽抄家。

虾仁经过了解，锦衣卫通过抄家总结出了一个规律，抄家会得到一些珠宝，将这些 $n$ 个珠宝排成一行，每个珠宝的种类为 $a_i$。 定义区间的珠宝差异度 $f(l, r)$ 的值为区间 $[l,r]$ 内珠宝的个数减去珠宝种类数，只要将差异度控制到 $k$，那么锦衣卫就能偷偷的拿走抄家得到的一部分珠宝。现在虾仁想知道有多少区间的珠宝差异度恰好等于 $k$，请你帮帮他，因为在大明当官太穷了！

简单来说，给定一个长为 $n$ 的序列，请计算：

输入格式

第一行两个整数 $n,k\ \left(1\le n\le 2\times 10^5,0\le k \le n\right)$，表示珠宝的个数和给定的 $k$ 值。

第二行输入 $n$ 个正整数 $a_i\ \left(1\le a_i \le 10^9\right)$ 代表每个珠宝所属种类。

输出格式

输出一个整数，表示有多少个区间能够满足珠宝差异度为 $k$。

样例输入1

3 0
2 2 1

样例输出1

4

样例输入2

3 2
1 1 1

样例输出2

1

样例输入3

10 2
9 3 3 8 2 8 7 1 5 8

样例输出3

10

样例输入4

15 3
1 3 7 2 7 14 7 11 11 9 5 4 1 3 12

样例输出4

16

样例解释

对于样例一：

满足条件的区间有：$[1,1],[1,2],[2,2],[3,3]$ 共 $4$ 个。

对于样例二：

满足条件的区间有：$[1,3]$ 共 $1$ 个。