#include <stdio.h>
#include <vector>
#include <deque>
 
#define FOR(i, a, b) for(int (i) = (a); (i) < (b); ++(i))
#define REP(i, n) FOR(i, 0, n)
#define rREP(i, n) for(int (i) = (n) - 1; (i) >= 0; --(i))

// UnionFind 木 ; 頂点 = 0, 1, 2, ...,  n-1
class UnionFindTree{
private:
    using Vint = std::vector<int>;
    const int n; // 集合の大きさ
    int kind; // 数
    Vint Parent; // 親のインデックスを指し示す
    Vint SetSize; // 各集合の大きさ(要素数)を保持する関数
public:
    // コンストラクタ
    UnionFindTree(int nn): n(nn), kind(nn){
        SetSize.resize(n, 1);
        Parent.resize(n);
        // 初めは, 全ての頂点は根である
        for(int i = 0; i < n; ++i) Parent[i] = i;
    }
    // デコンストラクタ
    ~UnionFindTree(void){}
    // 頂点 x の属する集合の根を返す関数
    int rootOf(int x){
        // x が 根であるなら終了
        if(Parent[x] == x) return x;
        // そうでないなら, 親を属する集合の根に付け替える
        return Parent[x] = rootOf(Parent[x]);
    }
    // 頂点 x, y を併合する
    void unite(int x, int y){
        int root_x = rootOf(x);
        int root_y = rootOf(y);
        // 異なる集合に属する場合
        if(root_x == root_y) return;
        if(SetSize[root_x] < SetSize[root_y]) std::swap(root_x, root_y);
        Parent[root_y] = root_x;
        SetSize[root_x] += SetSize[root_y];
        kind--;
    }
    // 頂点 x, y が 同じ集合に属しているかを判定する
    bool sameSet(int x, int y){
        return rootOf(x) == rootOf(y);
    }
    // 頂点 x の属する集合の要素数
    int sizeOf(int x){
        return SetSize[rootOf(x)];
    }
    int Kind(void){return kind;}
};

// スライド最小値を返す関数 O(N) : res[i] = min_{j ∈ [i, i+k)} A[j]
template <class Element>
std::vector<Element> slideMinimum(std::vector<Element>& A, const int k){
    const int n = A.size(); // 配列 A の長さ
    std::deque<int> deq;
    std::vector<Element> res(n); // [i, i+k)での最小値を求める
    for(int index = 0; index < n; ++index){
        while(not deq.empty() and A[deq.back()] >= A[index]) deq.pop_back();
        deq.push_back(index);
        if(index - k + 1 >= 0){
            res[index - k + 1] = A[deq.front()];
            if(deq.front() == index - k + 1) deq.pop_front();
        }
    }
    return res;
}
// スライド最大値を返す関数 O(N) : res[i] = min_{j ∈ [i, i+k)} A[j]
template <class Element>
std::vector<Element> slideMaximum(std::vector<Element>& A, const int k){
    const int n = A.size(); // 配列 A の長さ
    std::deque<int> deq;
    std::vector<Element> res(n); // [i, i+k)での最小値を求める
    for(int index = 0; index < n; ++index){
        while(not deq.empty() and A[deq.back()] <= A[index]) deq.pop_back();
        deq.push_back(index);
        if(index - k + 1 >= 0){
            res[index - k + 1] = A[deq.front()];
            if(deq.front() == index - k + 1) deq.pop_front();
        }
    }
    return res;
}

std::vector<int> A;


int main(void){
    int n, k; scanf("%d%d", &n, &k);
    A.resize(n); REP(i, n) scanf("%d", &A[i]);
    std::vector<int> SlideMin = slideMinimum(A, k-1);
    std::vector<int> SlideMax = slideMaximum(A, k-1);
    UnionFindTree UFT(n-k+2);
    for(int x = 0; x + k < n; ++x)
        if(A[x] <= SlideMin[x+1] and SlideMax[x+1] <= A[x+k]) UFT.unite(x, x+1);
    std::vector<int> S(n, 1);
    rREP(i, n-1) if(A[i] <= A[i+1]) S[i] = S[i+1] + 1;
    for(int x = 0; x <= n - k; ++x) if(S[x] >= k) UFT.unite(x, n-k+1);
    int res = UFT.Kind(); if(UFT.sizeOf(n-k+1) == 1) res--;
    printf("%d\n", res);
    return 0;
}

Measured memory_bytes: 4992