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;
#define rep(i,n) for(int i=0;i<n;i++)
typedef long long ll;
int main(){
    int n,k,P[200001];
    cin>>n>>k;
    rep(i,n) cin>>P[i];
    int a=1,b=0,x=0,ans=0;
    rep(i,n-1){
        if(P[i]<P[i+1]) a++;
        else a=1;
        if(a>=k) b++;
        if(a>k) x++;
    }
    set<int> A,B;
    int z;
    rep(i,k) A.insert(P[i]),B.insert(-P[i]);
    for(int i=k;i<n;i++){
        z=0;
        int c=P[i-k],d=P[i];
        if(*A.begin()!=c) z=1;
        A.erase(c);
        A.insert(d);
        B.erase(-c);
        B.insert(-d);
        if(*B.begin()!=-d) z=1;
        if(z) continue;
        ans++;
    }
    cout<<(n-k+1)-(ans+b-x)+(b>0);
}