E - Jingle, Jingle, Presents!!

2 secs 1024 MB
matcharate12's icon matcharate12

Story

🔔🎁

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

…

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

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

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

問題

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

  • Al,Al+1,…,ArA_l,A_{l+1},\dots ,A_r のうち、任意の整数 kk の出現する個数が KK 以下である

入力

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

NN KK
A1A_1 A2A_2 …\dots ANA_N

制約

  • 2≤N≤1052\le N\le 10^5
  • 1≤K≤1051\le K\le 10^5
  • 1≤Ai≤1031\le A_i\le 10^3

出力

答えを出力せよ。

入出力例

入力例1
5 1
1 2 3 3 5
出力例1
4

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

入力例2
5 5
1 2 3 4 5
出力例2
10

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

入力例3
14 2
3 1 4 1 5 9 2 6 5 3 5 8 9 7
出力例3
71

Submit


Go (1.21)