Problem: Snuke has a permutation (P_0,P_1,\cdots,P_{N-1}) of (0,1,\cdots,N-1).

Now, he will perform the following operation exactly once:

* Choose K consecutive elements in P and sort them in ascending order.



Find the number of permutations that can be produced as P after the operation.

Constraints

* 2 \leq N \leq 200000
* 2 \leq K \leq N
* 0 \leq P_i \leq N-1
* P_0,P_1,\cdots,P_{N-1} are all different.
* All values in input are integers.

Input

Input is given from Standard Input in the following format:


N K
P_0 P_1 \cdots P_{N-1}


Output

Print the number of permutations that can be produced as P after the operation.

Examples

Input

5 3
0 2 1 4 3


Output

2


Input

4 4
0 1 2 3


Output

1


Input

10 4
2 0 1 3 7 5 4 6 8 9


Output

6

Solution (in JAVA):

Solution:
import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int N = sc.nextInt();
		int K = sc.nextInt();
		int[] P = new int[N];
		for(int i=0; i<N; i++)
			P[i] = sc.nextInt();
		
		int ans = 1;
		TreeSet<Integer> ts = new TreeSet<>();
		for(int i=0; i<N; i++) {
			ts.add(P[i]);
			if(i>=K) {
				if(ts.last()!=P[i] || ts.first()!=P[i-K]) {
					ans++;
				}
				ts.remove(P[i-K]);
			}
		}
		
		int notChange=0;
		int cnt=1;
		for(int i=1; i<N; i++) {
			if(P[i-1]<P[i]) {
				cnt++;
				if(cnt==K)
					notChange++;
			} else {
				cnt=1;
			}
		}
		
		System.out.println(ans - (notChange>=2 ? notChange-1 : 0));
		sc.close();
	}
}