F - MEX2 Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 100 点

問題文

正整数 N、非負整数 K、長さ N の非負整数列 A=(A_{1},A_{2},\ldots,A_{N}) が与えられます。

整数組 (L,R) であって 1\leq L\leq R\leq N かつ \operatorname{mex}(\lbrace A_{L},A_{L+1},\ldots,A_{R}\rbrace)=K を満たすものの個数を計算してください。

mex の定義 非負整数の有限集合 S に対し、\operatorname{mex}(S) を x\not\in S である非負整数 x の最小値として定めます。

制約

  • 1\leq N\leq 2\times 10^{5}
  • 0\leq K\leq N
  • 0\leq A_i\leq N

入力

入力は以下の形式で標準入力から与えられます。

N K
A_{1} A_{2} \ldots A_{N}

出力

条件を満たす (L,R) の個数を出力してください。

入力例 1

5 2
0 1 2 1 0

出力例 1

2

条件を満たす (L,R) は (1,2) と (4,5) の 2 つです。

入力例 2

5 0
1 2 3 4 5

出力例 2

15

入力例 3

10 2
0 1 1 3 1 0 2 1 0 4

出力例 3

11