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(i = 0;i < n;++i)
#define all(v) v.begin(), v.end()
using ll = long long;

int main()
{
    ll i,j;
    ll n,k;
    cin >> n >> k;
    vector<ll> p(n);
    for(i = 0;i < n;++i){
        cin >> p.at(i);
    }

    ll cnt = 1;
    vector<bool> is_sorted(n,false);
    for(i = 1;i < n;++i){
        if(p.at(i-1) < p.at(i)) ++cnt;
        else cnt = 1;
        if(cnt >= k){
            is_sorted.at(i-(k-1)) = true;
        }
    }

    set<ll> s;
    for(i = 0;i < k;++i){
        s.insert(p.at(i));
    }
    ll ans = !is_sorted.at(0);
    for(i = 1;i + k - 1 < n;++i){
        s.erase(p.at(i-1));
        s.insert(p.at(i+k-1));
        if(!is_sorted.at(i) && !(p.at(i-1) < *s.begin() && p.at(i+k-1) == *s.rbegin())) ++ans;
    }
    for(i = 0;i < n;++i){
        if(is_sorted.at(i)){
            ++ans;
            break;
        }
    }
    cout << ans << endl;
    return 0;
}