← 返回题目列表

AtCoder · pakencamp_2023_day3_f

F. 第二个最小未出现数

中文机器翻译题面 查看原题

配点 : 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 的项目数。

墨西哥的定义 非负整数有限集 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