问题陈述
给定一个长度-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