Buggy python submission (verdict: Time Limit Exceeded):
import sys
import random
input = sys.stdin.readline

class Segment_tree():
    def __init__(self, n, arrange):
        self.inf = pow(2, 32)
        self.n = n
        self.arrange = arrange
        self.N = 1
        while self.N < self.n:
            self.N *= 2
        self.size = self.N * 2
        self.size -= 1
        self.N -= 1
        self.segment = [0]*(self.N) + self.arrange + [0]*(self.size-self.N-self.n)
        #この次の処理は、求められる動作に応じて変化させる。ここでは区間最小値問題のコードを書く。
        for i in range(self.N-1, -1, -1):
            self.segment[i] = min([self.segment[2*i+1], self.segment[2*i+2]])
        
    def undate(self, i, x):
        i += (self.N-1)
        self.segment[i] = x
        while i > 0:
            i = (i-1)//2
            self.segment[i] = min([self.segment[2*i+1], self.segment[2*i+2]])
        
    def find(self, a, b, k, l, r):
        if r <= a or b <= l:
            return self.inf
        elif a <= l and r <= b:
            return self.segment[k]
        else:
            find_l = self.find(a, b, 2*k+1, l, (l+r)//2)
            find_r = self.find(a, b, 2*k+2, (l+r)//2, r)
            return min([find_l, find_r])
    
    def count(self, l, r):
        return self.find(l, r, 0, 0, self.size-self.N)

class Segment_tree2():
    def __init__(self, n, arrange):
        self.inf = pow(2, 32)
        self.n = n
        self.arrange = arrange
        self.N = 1
        while self.N < self.n:
            self.N *= 2
        self.size = self.N * 2
        self.size -= 1
        self.N -= 1
        self.segment = [0]*(self.N) + self.arrange + [0]*(self.size-self.N-self.n)
        #この次の処理は、求められる動作に応じて変化させる。ここでは区間最小値問題のコードを書く。
        for i in range(self.N-1, -1, -1):
            self.segment[i] = max([self.segment[2*i+1], self.segment[2*i+2]])
        
    def undate(self, i, x):
        i += (self.N-1)
        self.segment[i] = x
        while i > 0:
            i = (i-1)//2
            self.segment[i] = max([self.segment[2*i+1], self.segment[2*i+2]])
        
    def find(self, a, b, k, l, r):
        if r <= a or b <= l:
            return 0
        elif a <= l and r <= b:
            return self.segment[k]
        else:
            find_l = self.find(a, b, 2*k+1, l, (l+r)//2)
            find_r = self.find(a, b, 2*k+2, (l+r)//2, r)
            return max([find_l, find_r])
    
    def count(self, l, r):
        return self.find(l, r, 0, 0, self.size-self.N)



def solve(n, k, p):
    segment_min = Segment_tree(n, p)
    segment_max = Segment_tree2(n, p)
    
    res = n-k+1
    for i in range(n-k):
        x, y = p[i], p[k+i]
        a = segment_min.count(i+1, k+i-1)
        b = segment_max.count(i+1, k+i-1)
        if x < a and b < y:
            res -= 1
    
    return res

def solve2(n, a):
    res = 1
    for i in range(n-2):
        if (a[i] > a[i+1]) or (a[i+1] > a[i+2]):
            res += 1
    return res
    
def main():
    n, k = map(int, input().split())
    p = list(map(int, input().split()))
    
    if k == 2:
        ans = solve2(n, p)
    else:
        ans = solve(n, k, p)
    print(ans)
    
    
if __name__ == "__main__":
    main()


Fixed submission:
import sys
from heapq import *
input = sys.stdin.readline


def solve(n, k, p):
    res = n-k+1
    count = 0
    length = 1
    
    judge_max = [-x for x in p[:k]]
    judge_min = p[:k]
    heapify(judge_max)
    heapify(judge_min)
    already = [False]*n
    
    for i in range(k-1):
        if p[i] < p[i+1]:
            length += 1
        else:
            length = 1
            
    if length == k:
        count += 1
    
    for i in range(k-1, n-1):
        if p[i] < p[i+1]:
            length += 1
        else:
            length = 1
        
        already[p[i-k+1]] = True
        while True:
            vmax = -judge_max[0]
            if already[vmax]:
                heappop(judge_max)
                continue
            else:
                break
        while True:
            vmin = judge_min[0]
            if already[vmin]:
                heappop(judge_min)
                continue
            else:
                break
        if p[i-k+1] < vmin and vmax < p[i+1]:
            res -= 1
        
        elif length >= k:
            if count:
                res -= 1
            count += 1
        heappush(judge_max, -p[i+1])
        heappush(judge_min, p[i+1])
    
    return res

    
def main():
    n, k = map(int, input().split())
    p = list(map(int, input().split()))
    
    ans = solve(n, k, p)
    print(ans)


if __name__ == "__main__":
    main()