← 返回题目列表

AtCoder · past21_i

I. 查找排列

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

问题陈述

给定一个长度-N 整数序列 A=(A_1,A_2,\dots,A_N) 和一个整数 K, 找到(连续)子数组的数量 A 是以下排列 1,2,\dots,K。 换句话说,找到之间的整数个数 1 和 N-K+1,包含在内,这样 (A_{i},A_{i+1},\dots,A_{i+K-1}) 是一个排列 1,2,\dots,K.

约束

  • 1 \leq K \leq N \leq 2 \times 10^5
  • 1 \leq A_i \leq K
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N K
A_1 A_2 \dots A_N

输出

打印答案。


示例输入 1

5 3
1 2 1 3 2

示例输出 1

2

其中长度-3 的子数组 A,这两个是排列 1,2,3: (A_2,A_3,A_4)=(2,1,3),(A_3,A_4,A_5)=(1,3,2).


示例输入 2

5 3
3 1 1 2 2

示例输出 2

0

示例输入 3

4 2
1 2 1 2

示例输出 3

3

示例输入 4

1 1
1

示例输出 4

1