Story

🔔🎁

summerrate君は悪行を働いたようです。

…

シャンシャンシャン…なんか鈴の音がしますね。 Xmasrate君は、クリスマスを楽しみにしている子供たちにプレゼントを渡す準備をしています。

それに欠かせないのがプレゼント選びですが、今回は雪上のベルトコンベアに流れてくるプレゼントから選びます。プレゼントの柄はいくつか種類があります。 プレゼント選びは、好きなものを選ぶことはできませんが、範囲を指定すればその範囲のプレゼントを運ぶことになります。 しかし同じ柄のプレゼントがいくつもあると嫌です。

「子どもには、やっぱりカラフルなプレゼントじゃな！単色は私がつまらないと思うからダメだ！！」

問題

長さ $N$ の数列 $A$ が与えられます。以下の条件を満たす整数の組 $(l,r)\ (1\le l\lt r\le N)$ はいくつありますか？

• $A_l,A_{l+1},\dots ,A_r$ のうち、任意の整数 $k$ の出現する個数が $K$ 以下である

入力

入力は以下の形式で与えられる。

制約

• $2\le N\le 10^5$
• $1\le K\le 10^5$
• $1\le A_i\le 10^3$

出力

答えを出力せよ。

入出力例

5 1
1 2 3 3 5

4

$(l,r)=(1,2),(1,3),(2,3),(4,5)$ の $4$ つの組が条件を満たします。

5 5
1 2 3 4 5

10

すべての組が条件を満たします。

14 2
3 1 4 1 5 9 2 6 5 3 5 8 9 7

71