#include <cassert>
#include <iterator>

template <class monoid>
class deque_aggregation
{
    template <bool left_operand_added>
    class stack_aggregation
    {
        friend deque_aggregation;
        struct data { monoid value, acc; };
        size_t capacity;
        data *stack, *end, *itr;
        bool top_referred;

        void recalc()
        {
            if(top_referred)
            {
                assert(itr != stack);
                top_referred = false;
                monoid top_val{top().value};
                pop();
                push(top_val);
            }
        }

    public:
        stack_aggregation() : capacity(1), stack(new data[1]), end(std::next(stack)), itr(stack), top_referred() {}
        ~stack_aggregation() { delete[] stack; }

        bool empty() const { return stack == itr; }
        size_t size() const { return itr - stack; }

        // copy of the element at the index.
        data operator[](size_t index) const
        {
            assert(index < size());
            recalc();
            return stack[index];
        }

        // reference to the last element
        data &top()
        {
            assert(itr != stack);
            top_referred = true;
            return *std::prev(itr);
        }

        void pop()
        {
            assert(itr != stack);
            --itr;
            top_referred = false;
        }

        void push(const monoid &mono)
        {
            recalc();
            if(itr == end)
            {
                data *tmp = new data[capacity << 1];
                std::swap(stack, tmp);
                end = (itr = std::copy(tmp, tmp + capacity, stack)) + capacity;
                capacity <<= 1;
                delete[] tmp;
            }
            if(left_operand_added) *itr = data{mono, mono + fold()};
            else *itr = data{mono, fold() + mono};
            ++itr;
        }

        monoid fold()
        {
            if(itr == stack) return monoid();
            recalc();
            return std::prev(itr)->acc;
        }
    }; // class stack_aggregation

    stack_aggregation<true> left;
    stack_aggregation<false> right;

    void balance_to_left()
    {
        if(!left.empty() || right.empty()) return;
        left.recalc(); right.recalc();
        size_t mid = (right.size() + 1) >> 1;
        auto *itr = right.stack + mid;
        do { left.push((--itr)->value); } while(itr != right.stack);
        monoid acc;
        for(auto *p = right.stack + mid; p != right.itr; ++p, ++itr)
        {
            *itr = {p->value, acc = acc + p->value};
        }
        right.itr = itr;
    }

    void balance_to_right()
    {
        if(!right.empty() || left.empty()) return;
        left.recalc(); right.recalc();
        size_t mid = (left.size() + 1) >> 1;
        auto *itr = left.stack + mid;
        do { right.push((--itr)->value); } while(itr != left.stack);
        monoid acc;
        for(auto *p = left.stack + mid; p != left.itr; ++p, ++itr)
        {
            *itr = {p->value, acc = p->value + acc};
        }
        left.itr = itr;
    }

public:
    bool empty() const { return left.empty() && right.empty(); }
    size_t size() const { return left.size() + right.size(); }

    // reference to the first element.
    monoid &front() { assert(!empty()); return balance_to_left(), left.top().value; }

    // reference to the last element.
    monoid &back() { assert(!empty()); return balance_to_right(), right.top().value; }

    // copy of the element at the index.
    monoid operator[](size_t index) const
    {
        assert(index < left.size() + right.size());
        return index < left.size() ? left[index].value : right[index - left.size()].value;
    }

    void push_front(const monoid &mono) { left.push(mono); }

    void push_back(const monoid &mono) { right.push(mono); }

    void pop_front()
    {
        assert(!empty());
        balance_to_left();
        left.pop();
    }

    void pop_back()
    {
        assert(!empty());
        balance_to_right();
        right.pop();
    }

    monoid fold() { return left.fold() + right.fold(); }
}; // class deque_aggregation


#include <cstdio>
using namespace std;

main()
{
    struct mino
    {
        int *ptr;
        mino(int *p=nullptr) : ptr(p) {}
        mino operator+(const mino& rhs) const
        {
            if(!ptr) return rhs;
            if(!rhs.ptr) return *this;
            return *ptr<*rhs.ptr ? *this : rhs;
        }
    };

    struct mano
    {
        int *ptr;
        mano(int *p=nullptr) : ptr(p) {}
        mano operator+(const mano& rhs) const
        {
            if(!ptr) return rhs;
            if(!rhs.ptr) return *this;
            return *ptr>*rhs.ptr ? *this : rhs;
        }
    };

    deque_aggregation<mino> min_que;
    deque_aggregation<mano> max_que;

    int n,k; scanf("%d%d",&n,&k);
    int ary[1<<18];
    bool sorted=0;
    int ans=0;

    for(int i=0; i<n; ++i)
    {
        int *const now=ary+i;
        scanf("%d",now);
        int flag=0;

        if(i>=k)
        {
            if(now-min_que.front().ptr == k)
            {
                min_que.pop_front();
            }
            else
            {
                flag=1;
            }

            if(now-max_que.front().ptr == k) max_que.pop_front();
        }

        while(!min_que.empty() && *min_que.back().ptr>*now)  min_que.pop_back();
        min_que.push_back(now);

        while(!max_que.empty() && *max_que.back().ptr<*now)  max_que.pop_back();
        if(!max_que.empty()) flag=1;
        max_que.push_back(now);

        if(i<k)
        {
            flag=0;
            if(i+1==k) flag=1;
        }

        if(min_que.size()==k)
        {
            flag=0;
            sorted=1;
        }

        if(flag)
        {
            ans++;
            // printf("%d\n",i);
        }
    }

    ans+=sorted;
    printf("%d\n",ans);
}

Measured memory_bytes: 9196