#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <set>
#include <limits>
#include <functional>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> P;
typedef pair<int, ll> Pl;
const double PI = 3.1415926535897932;   // acos(-1)
const double EPS = 1e-15;
const int mod = 1e+9 + 7;
const int INF = 1e+9;

bool p_n[200005];
const int MAXN = 200005;
int par[MAXN];
int depth[MAXN];

void init(int n){
    for(int i = 0; i < n; ++i){
        par[i] = i;
        depth[i] = 0;
    }
}

int find(int x){
    if(par[x] == x){
        return x;
    }
    else{
        return par[x] = find(par[x]);
    }
}

void unite(int x, int y){
    x = find(x);
    y = find(y);

    if(x == y)  return;

    if(depth[x] < depth[y]){
        par[x] = y;
    }
    else{
        par[y] = x;
        if(depth[x] == depth[y])  ++depth[x];
    }
}

bool same(int x, int y){
    return find(x) == find(y);
}

template<typename Monoid>
struct SegmentTree{
    using F = function<Monoid(Monoid, Monoid)>;

    int sz;
    vector<Monoid> seg;

    const F f;      // モノイドに対して二項演算を行う関数オブジェクト
    const Monoid M1;

    SegmentTree(int n, const F f, const Monoid &M1) : f(f), M1(M1){
        sz = 1;
        while(sz < n)   sz <<= 1;
        seg.assign(2 * sz, M1);
    }

    void set(int k, const Monoid &x){
        seg[k + sz] = x;
    }

    void build(){
        for(int k = sz - 1; k > 0; --k){
            seg[k] = f(seg[k << 1], seg[k << 1 | 1]);
        }
    }

    void update(int k, const Monoid &x){
        k += sz;
        seg[k] = x;
        while(k >>= 1){
            seg[k] = f(seg[k << 1], seg[k << 1 | 1]);
        }
    }

    Monoid query(int a, int b){
        Monoid L = M1, R = M1;
        for(a += sz, b += sz; a < b; a >>= 1, b >>= 1){
            if(a & 1)   L = f(L, seg[a++]);
            if(b & 1)   R = f(seg[--b], R);
        }
        return f(L, R);
    }

    Monoid operator[](const int &k) const{
        return seg[k + sz];
    }

    // type=true : find_last
    // type=false : find_first
    template<typename C>
    int find_subtree(int a, const C &check, Monoid &M, bool type){
        while(a < sz){
            Monoid nxt = type ? f(seg[a << 1 | type], M) : f(M, seg[a << 1 | type]);
            if(check(nxt))  a = a << 1 | type;
            else M = nxt, a = 2 * a + 1 - type;
        }
        return a = sz;
    }

    template<typename C>
    int find_first(int a, const C &check){
        Monoid L = M1;
        if(a <= 0){
            if(check(f(L, seg[1]))) return find_subtree(1, check, L, false);
            return -1;
        }
        int b = sz;
        for(a += sz, b += sz; a < b; a >>= 1, b >>= 1){
            if(a & 1){
                Monoid nxt = f(L, seg[a]);
                if(check(nxt))  return find_subtree(a, check, L, false);
                L = nxt;
                ++a;
            }
        }
        return -1;
    }

    template<typename C>
    int find_last(int b, const C &check){
        Monoid R = M1;
        if(b >= sz){
            if(check(f(seg[1], R))) return find_subtree(1, check, R, true);
            return -1;
        }
        int a = sz;
        for(b += sz; a < b; a >>= 1, b >>= 1){
            if(b & 1){
                Monoid nxt = f(seg[--b], R);
                if(check(nxt))  return sub_tree(b, check, R, true);
                R = nxt;
            }
        }
        return -1;
    }
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k;
    cin >> n >> k;
    vector<int> p(n);
    // 区間最小値を得るセグメント木
    SegmentTree<int> seg_min(n, [](int a, int b){return min(a, b);}, numeric_limits<int>::max());
    // 区間最大値を得るセグメント木
    SegmentTree<int> seg_max(n, [](int a, int b){return max(a, b);}, -1);
    for(int i = 0; i < n; ++i){
        cin >> p[i];
        seg_min.set(i, p[i]);
        seg_max.set(i, p[i]);
    }
    // セグメント木の構築
    seg_min.build();
    seg_max.build();
    // Union-Find の初期化
    init(n);

    // k 個の区間が元々昇順であるかどうか
    for(int i = 0; i < n-1; ++i){
        if(p[i+1] - p[i] > 0)   p_n[i] = true;
        else    p_n[i] = false;     // p[i+1] - p[i] < 0
    }
    vector<int> ascending;      // 元々昇順に並んでいる k 個の区間の左端
    int p_cnt = 0, n_cnt = 0;
    for(int i = 0; i < k-1; ++i){
        if(p_n[i])  ++p_cnt;
        else    ++n_cnt;
    }
    if(p_cnt == k-1)    ascending.push_back(0);
    int left = 0, right = k-1;    // [left, right)
    while(left < n - k){
        if(p_n[left])   --p_cnt;
        else    --n_cnt;
        ++left;
        if(p_n[right])  ++p_cnt;
        else    ++n_cnt;
        ++right;
        if(p_cnt == k-1)    ascending.push_back(left);
    }
    if(ascending.size() != 0){
        int u = ascending[0];
        for(int i = 1; i < (int)ascending.size(); ++i){
            int v = ascending[i];
            unite(u, v);
        }
    }

    // 区間最小値と区間最大値を用いて、隣接する区間が操作した結果一緒になるか判定する
    for(int i = 0; i < n-k; ++i){
        int min_e = seg_min.query(i, i+k);
        int max_e = seg_max.query(i+1, i+k+1);
        if(min_e == p[i] && max_e == p[i+k])    unite(i, i+1);
    }

    // Union-Find のグループ数を出力する
    int res = 0;
    set<int> s;
    for(int i = 0; i <= n-k; ++i){
        int v = find(i);
        if(s.find(v) == s.end()){
            ++res;
            s.insert(v);
        }
    }

    cout << res << endl;
}

Measured memory_bytes: 16256