Buggy python submission (verdict: Runtime Error):
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]

    N,K = LI()
    P = LI()

    class Node:
        def __init__(self, x):
            self.data = x
            self.count = 1
            self.left = None
            self.right = None

    def insert(node, x):
        if node is None: return Node(x)
        if node.data == x:
            node.count += 1
        elif x < node.data:
            node.left = insert(node.left, x)
        else:
            node.right = insert(node.right, x)
        return node

    def search_min(node):
        if node.left is None: return node.data
        return search_min(node.left)

    def search_max(node):
        if node.right is None: return node.data
        return search_max(node.right)

    def delete_min(node):
        if node.left is None:
            if node.count > 1:
                node.count -= 1
            else:
                return node.right
        else:
            node.left = delete_min(node.left)
        return node

    def delete(node, x):
        if node:
            if x == node.data:
                if node.count > 1:
                    node.count -= 1
                elif node.left is None:
                    return node.right
                elif node.right is None:
                    return node.left
                else:
                    node.data = search_min(node.right)
                    node.right = delete_min(node.right)
            elif x < node.data:
                node.left = delete(node.left, x)
            else:
                node.right = delete(node.right, x)
        return node

    root = None
    cnt = 0
    bp = -1
    for i in range(K):
        root = insert(root,P[i])
        if P[i] > bp:
            cnt += 1
        else:
            cnt = 0
        bp = P[i]

    if cnt >= K:
        flg = 1
        ans = 0
    else:
        flg = 0
        ans = 1
    for i in range(1,N-K):
        if P[i+K-1] > bp:
            cnt += 1
        else:
            cnt = 0
        bp = P[i+K-1]
        if search_min(root) == P[i-1] and search_max(root) < P[i+K-1] or cnt >= K:
            flg = 1
        else:
            ans +=1
        root = insert(root,P[i+K-1])
        root = delete(root,P[i-1])

    print(ans+flg)


if __name__ == '__main__':
    main()

Fixed submission:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]

    N,K = LI()
    P = LI()

    N0 = 2 ** (N.bit_length())
    st1 = [0] * (2 * N0)
    st2 = [0] * (2 * N0)

    i = N0-1
    for x in P:
        st1[i] = st2[i] = x
        i += 1


    for i in range(N0-2,-1,-1):
        st1[i] = max(st1[i*2+1],st1[i*2+2])
        st2[i] = min(st2[i*2+1],st2[i*2+2])

    def query_max(l, r):
        L = l + N0;
        R = r + N0
        ret = 0
        while L < R:
            if L % 2:
                ret = max(ret, st1[L - 1])
                L += 1
            if R % 2:
                R -= 1
                ret = max(ret, st1[R - 1])
            L //= 2;
            R //= 2
        return ret


    def query_min(l, r):
        L = l + N0;
        R = r + N0
        ret = N + 1  # max value
        while L < R:
            if L % 2:
                ret = min(ret, st2[L - 1])
                L += 1
            if R % 2:
                R -= 1
                ret = min(ret, st2[R - 1])
            L //= 2;
            R //= 2
        return ret


    ans = 0
    cnt = 0
    flg = 0
    bp = N
    for i in range(N):
        if P[i] > bp:
            cnt += 1
        else:
            cnt = 0
        bp = P[i]

        if i < K - 1: continue

        if cnt >= K-1:
            flg = 1
        elif i >= K and query_min(i-K,i) == P[i-K] and query_max(i-K+1,i+1) == P[i]:
            pass
        else:
            ans += 1

    print(ans+flg)


if __name__ == '__main__':
    main()