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 = N-K+1;
		int nochange = 0, x = 1;
		for(int i = 1; i < N; i++) {
			if(P[i] > P[i-1]) {
				x++;
				if(i == N-1)
					if(x >= K)
						nochange++;
			}
			else {
				if(x >= K)
					nochange++;
				x = 1;
			}
		}
		if(nochange > 0)
			ans = ans - nochange + 1;
		TreeSet<Integer> ts = new TreeSet<>();
		for(int i = 0; i < K; i++)
			ts.add(P[i]);
		for(int i = 0; i < N-K; i++) {
			if(ts.first() == P[i] && P[i+K] > ts.last())
				ans--;
			ts.remove(P[i]);
			ts.add(P[i+K]);
		}
		System.out.println(ans);

	}

}