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 N 200200

int n, K, p[N], nxt[N], prv[N];
bool vis[N];

int main() {
    cin >> n >> K;
    for (int i = 1; i <= n; i ++) cin >> p[i], p[i] ++;
    p[0] = n + 1;
    for (int i = 1; i <= n; i ++) {
        prv[i] = i - 1;
        while (p[prv[i]] < p[i]) prv[i] = prv[prv[i]];
    }
    for (int i = n; i; i --) {
        nxt[i] = i + 1;
        while (p[nxt[i]] > p[i]) nxt[i] = nxt[nxt[i]];
    }
    int ans = 0;
    for (int i = 1, j = 1; i <= n; i = j) {
        for (j ++; j <= n && p[j] > p[j-1]; j ++);
        for (int k = i; k + K <= j; k ++) vis[k] = ans = 1;
    }
    for (int i = 1, j; i <= n - K + 1; i ++) if (!vis[i]) {
        for (j = i; j <= n - K + 1; j ++) {
            if (vis[j] || nxt[j] <= j + K || prv[j+K] >= j) break;
        }
        ans ++; i = j;
    }
    cout << ans << endl;
}