/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
問題文
長さ N の整数列 A=(A_1,A_2,\dots,A_N) と整数 K が与えられます。 A の連続部分列であって、1,2,\dots,K の並べ替えであるものの個数を求めてください。 すなわち、1 以上 N-K+1 以下の整数 i であって、(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
A の長さ 3 の連続部分列のうち、1,2,3 の並べ替えであるものは (A_2,A_3,A_4)=(2,1,3),(A_3,A_4,A_5)=(1,3,2) の 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
Problem Statement
Given a length-N integer sequence A=(A_1,A_2,\dots,A_N) and an integer K, find the number of (consecutive) subarrays of A that are permutations of 1,2,\dots,K. In other words, find the number of integers between 1 and N-K+1, inclusive, such that (A_{i},A_{i+1},\dots,A_{i+K-1}) is a permutation of 1,2,\dots,K.
Constraints
- 1 \leq K \leq N \leq 2 \times 10^5
- 1 \leq A_i \leq K
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N K A_1 A_2 \dots A_N
Output
Print the answer.
Sample Input 1
5 3 1 2 1 3 2
Sample Output 1
2
Among the length-3 subarrays of A, these two are permutations of 1,2,3: (A_2,A_3,A_4)=(2,1,3),(A_3,A_4,A_5)=(1,3,2).
Sample Input 2
5 3 3 1 1 2 2
Sample Output 2
0
Sample Input 3
4 2 1 2 1 2
Sample Output 3
3
Sample Input 4
1 1 1
Sample Output 4
1