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 CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;

int A[200009], F[200009];
bool C[200009];

void upd(int x, int y) {
    for(int i=x; i<=200000; i+=(i&-i)) F[i] += y;
}

int get(int x) {
    int ret = 0;
    for(int i=x; i>=1; i-=(i&-i)) ret += F[i];
    return ret;
}

int main() {
    long long ans = 0;
    int N, K; scanf("%d%d",&N,&K);
    C[K] = 1;
    for(int i=1; i<=N; i++) {
        scanf("%d", &A[i]);
        if(i > K) {
            upd(A[i-K] + 1, -1);
            if(get(A[i-K])) C[i] = 1;
            if(K - get(A[i]) - 1) C[i] = 1;
        }
        upd(A[i] + 1, +1);
        if(C[i]) ++ans;
    }
    int l = 1, c = 0;
    for(int i=1; i<=N; i++) {
        if(i >= 2 && A[i-1] > A[i]) l = i;
        if(i - l + 1 >= K && C[i]) ++c;
    }
    printf("%lld", ans - max(0, c-1));
    return 0;
}