Buggy python submission (verdict: Time Limit Exceeded):
# import numpy as np

n,k = map(int, input().split())
p_list = tuple(map(int, input().split()))

p_before = 200001
up = 0

mins = [0]*(n+1-k)
maxs = [0]*(n+1-k)

for i in range(n+1-k):
    temp = p_list[i:i+k]
    mins[i] = min(temp)
    maxs[i] = max(temp)

mins = mins[:-1]
maxs = maxs[1:]

origin = 0
not_origin = 0

for p in p_list[:k]:
    if p_before < p:
        up += 1
    else:
        up=0
    p_before = p*1

    if p == p_list[k-1]:
        if up >= k-1:
            origin = 1
        else:
            not_origin = 1


for p,i in zip(p_list[k:], range(k,n)):
    if p_before < p:
        up += 1
    else:
        up=0
    p_before = p*1

    if up >= k-1:
        origin = 1
    else:
        if p_list[i-k] == mins[i-k]:
            if p_list[i] != maxs[i-k]:
                not_origin += 1
        else:
            not_origin += 1


print(origin + not_origin)


Fixed submission:
n,k = map(int,input().split())
p = tuple(map(int,input().split()))

class Seg_min():
    def __init__(self,x):
        #####単位元######
        self.ide_ele_min = 10**10
        self.func = min

        self.n = len(x)

        #num_max:n以上の最小の2のべき乗
        self.num_max =2**(self.n-1).bit_length()
        self.x = [self.ide_ele_min]*2*self.num_max

        for i,num in enumerate(x, self.num_max):
            self.x[i] = num
        for i in range(self.num_max-1,0,-1):
            self.x[i] = self.func(self.x[i<<1],self.x[(i<<1) + 1])

    def update(self,i,x):
        i += self.num_max
        self.x[i] = x
        while(x>0):
            i = i//2
            self.x[i] = self.func(self.x[i<<1],self.x[(i<<1) + 1])

    def query(self,i,j):
        res = self.ide_ele_min
        if i>=j:
            return res
        i += self.num_max
        j += self.num_max -1
        while(i<=j):
            if(i==j):
                res = self.func(res,self.x[i])
                break
            if(i&1):
                res = self.func(res,self.x[i])
                i += 1
            if(not j&1):
                res = self.func(res,self.x[j])
                j -= 1
            i = i>>1
            j = j>>1
        return res

class Seg_max():
    def __init__(self,x):
        #####単位元######
        self.ide_ele_min = 10**10 * -1
        self.func = max

        self.n = len(x)

        #num_max:n以上の最小の2のべき乗
        self.num_max =2**(self.n-1).bit_length()
        self.x = [self.ide_ele_min]*2*self.num_max

        for i,num in enumerate(x, self.num_max):
            self.x[i] = num
        for i in range(self.num_max-1,0,-1):
            self.x[i] = self.func(self.x[i<<1],self.x[(i<<1) + 1])

    def update(self,i,x):
        i += self.num_max
        self.x[i] = x
        while(x>0):
            i = i//2
            self.x[i] = self.func(self.x[i<<1],self.x[(i<<1) + 1])

    def query(self,i,j):
        res = self.ide_ele_min
        if i>=j:
            return res
        i += self.num_max
        j += self.num_max -1
        while(i<=j):
            if(i==j):
                res = self.func(res,self.x[i])
                break
            if(i&1):
                res = self.func(res,self.x[i])
                i += 1
            if(not j&1):
                res = self.func(res,self.x[j])
                j -= 1
            i = i>>1
            j = j>>1
        return res

seg_min = Seg_min(p)
seg_max = Seg_max(p)

natural = 0
ans = 0

head = 0
for i in range(1,n):
    if(p[i]<p[i-1]):
        head = i

    if(i-head >= k-1):
        natural = 1
        continue

    if(i==k-1):
        ans +=1
    if(i<k):
        continue
    ans += 1

    left = seg_min.query(i-k,i)
    right = seg_max.query(i-k+1,i+1)
    if(left==p[i-k])&(right==p[i]):
        ans -= 1

print(ans+natural)

Buggy python submission (verdict: Runtime Error):
# import numpy as np

n,k = map(int, input().split())
p_list = tuple(map(int, input().split())))

p_before = 200001
up = 0

mins = [0]*(n+1-k)
maxs = [0]*(n+1-k)

for i in range(n+1-k):
    temp = p_list[i:i+k]
    mins[i] = min(temp)
    maxs[i] = max(temp)

mins = mins[:-1]
maxs = maxs[1:]

origin = 0
not_origin = 0

for p in p_list[:k]:
    if p_before < p:
        up += 1
    else:
        up=0
    p_before = p*1

    if p == p_list[k-1]:
        if up >= k-1:
            origin = 1
        else:
            not_origin = 1


for p,i in zip(p_list[k:], range(k,n)):
    if p_before < p:
        up += 1
    else:
        up=0
    p_before = p*1

    if up >= k-1:
        origin = 1
    else:
        if p_list[i-k] == mins[i-k]:
            if p_list[i] != maxs[i-k]:
                not_origin += 1
        else:
            not_origin += 1


print(origin + not_origin)


Fixed submission:
n,k = map(int,input().split())
p = tuple(map(int,input().split()))

class Seg_min():
    def __init__(self,x):
        #####単位元######
        self.ide_ele_min = 10**10
        self.func = min

        self.n = len(x)

        #num_max:n以上の最小の2のべき乗
        self.num_max =2**(self.n-1).bit_length()
        self.x = [self.ide_ele_min]*2*self.num_max

        for i,num in enumerate(x, self.num_max):
            self.x[i] = num
        for i in range(self.num_max-1,0,-1):
            self.x[i] = self.func(self.x[i<<1],self.x[(i<<1) + 1])

    def update(self,i,x):
        i += self.num_max
        self.x[i] = x
        while(x>0):
            i = i//2
            self.x[i] = self.func(self.x[i<<1],self.x[(i<<1) + 1])

    def query(self,i,j):
        res = self.ide_ele_min
        if i>=j:
            return res
        i += self.num_max
        j += self.num_max -1
        while(i<=j):
            if(i==j):
                res = self.func(res,self.x[i])
                break
            if(i&1):
                res = self.func(res,self.x[i])
                i += 1
            if(not j&1):
                res = self.func(res,self.x[j])
                j -= 1
            i = i>>1
            j = j>>1
        return res

class Seg_max():
    def __init__(self,x):
        #####単位元######
        self.ide_ele_min = 10**10 * -1
        self.func = max

        self.n = len(x)

        #num_max:n以上の最小の2のべき乗
        self.num_max =2**(self.n-1).bit_length()
        self.x = [self.ide_ele_min]*2*self.num_max

        for i,num in enumerate(x, self.num_max):
            self.x[i] = num
        for i in range(self.num_max-1,0,-1):
            self.x[i] = self.func(self.x[i<<1],self.x[(i<<1) + 1])

    def update(self,i,x):
        i += self.num_max
        self.x[i] = x
        while(x>0):
            i = i//2
            self.x[i] = self.func(self.x[i<<1],self.x[(i<<1) + 1])

    def query(self,i,j):
        res = self.ide_ele_min
        if i>=j:
            return res
        i += self.num_max
        j += self.num_max -1
        while(i<=j):
            if(i==j):
                res = self.func(res,self.x[i])
                break
            if(i&1):
                res = self.func(res,self.x[i])
                i += 1
            if(not j&1):
                res = self.func(res,self.x[j])
                j -= 1
            i = i>>1
            j = j>>1
        return res

seg_min = Seg_min(p)
seg_max = Seg_max(p)

natural = 0
ans = 0

head = 0
for i in range(1,n):
    if(p[i]<p[i-1]):
        head = i

    if(i-head >= k-1):
        natural = 1
        continue

    if(i==k-1):
        ans +=1
    if(i<k):
        continue
    ans += 1

    left = seg_min.query(i-k,i)
    right = seg_max.query(i-k+1,i+1)
    if(left==p[i-k])&(right==p[i]):
        ans -= 1

print(ans+natural)

Buggy python submission (verdict: Time Limit Exceeded):
n,k = map(int, input().split())
p_list = tuple(map(int, input().split()))

p_before = 200001
up = 0

origin = 0
not_origin = 0

for p in p_list[:k]:
    if p_before < p:
        up += 1
    else:
        up=0
    p_before = p*1

    if p == p_list[k-1]:
        if up >= k-1:
            origin = 1
        else:
            not_origin = 1


for p,i in zip(p_list[k:], range(k,n)):
    if p_before < p:
        up += 1
    else:
        up=0
    p_before = p*1

    if up >= k-1:
        origin = 1
    else:
        if p_list[i-k] == min(p_list[(i-k):i]):
            if p_list[i] != max(p_list[(i-k+1):(i+1)]):
                not_origin += 1
        else:
            not_origin += 1


print(origin + not_origin)


Fixed submission:
n,k = map(int,input().split())
p = tuple(map(int,input().split()))

class Seg_min():
    def __init__(self,x):
        #####単位元######
        self.ide_ele_min = 10**10
        self.func = min

        self.n = len(x)

        #num_max:n以上の最小の2のべき乗
        self.num_max =2**(self.n-1).bit_length()
        self.x = [self.ide_ele_min]*2*self.num_max

        for i,num in enumerate(x, self.num_max):
            self.x[i] = num
        for i in range(self.num_max-1,0,-1):
            self.x[i] = self.func(self.x[i<<1],self.x[(i<<1) + 1])

    def update(self,i,x):
        i += self.num_max
        self.x[i] = x
        while(x>0):
            i = i//2
            self.x[i] = self.func(self.x[i<<1],self.x[(i<<1) + 1])

    def query(self,i,j):
        res = self.ide_ele_min
        if i>=j:
            return res
        i += self.num_max
        j += self.num_max -1
        while(i<=j):
            if(i==j):
                res = self.func(res,self.x[i])
                break
            if(i&1):
                res = self.func(res,self.x[i])
                i += 1
            if(not j&1):
                res = self.func(res,self.x[j])
                j -= 1
            i = i>>1
            j = j>>1
        return res

class Seg_max():
    def __init__(self,x):
        #####単位元######
        self.ide_ele_min = 10**10 * -1
        self.func = max

        self.n = len(x)

        #num_max:n以上の最小の2のべき乗
        self.num_max =2**(self.n-1).bit_length()
        self.x = [self.ide_ele_min]*2*self.num_max

        for i,num in enumerate(x, self.num_max):
            self.x[i] = num
        for i in range(self.num_max-1,0,-1):
            self.x[i] = self.func(self.x[i<<1],self.x[(i<<1) + 1])

    def update(self,i,x):
        i += self.num_max
        self.x[i] = x
        while(x>0):
            i = i//2
            self.x[i] = self.func(self.x[i<<1],self.x[(i<<1) + 1])

    def query(self,i,j):
        res = self.ide_ele_min
        if i>=j:
            return res
        i += self.num_max
        j += self.num_max -1
        while(i<=j):
            if(i==j):
                res = self.func(res,self.x[i])
                break
            if(i&1):
                res = self.func(res,self.x[i])
                i += 1
            if(not j&1):
                res = self.func(res,self.x[j])
                j -= 1
            i = i>>1
            j = j>>1
        return res

seg_min = Seg_min(p)
seg_max = Seg_max(p)

natural = 0
ans = 0

head = 0
for i in range(1,n):
    if(p[i]<p[i-1]):
        head = i

    if(i-head >= k-1):
        natural = 1
        continue

    if(i==k-1):
        ans +=1
    if(i<k):
        continue
    ans += 1

    left = seg_min.query(i-k,i)
    right = seg_max.query(i-k+1,i+1)
    if(left==p[i-k])&(right==p[i]):
        ans -= 1

print(ans+natural)

Buggy python submission (verdict: Time Limit Exceeded):
n,k = map(int, input().split())
p_list = list(map(int, input().split()))

p_before = 200001
up = 0

mins = [0]*(n+1-k)
maxs = [0]*(n+1-k)

for i in range(n+1-k):
    temp = p_list[i:i+k]
    mins[i] = min(temp)
    maxs[i] = max(temp)

mins = mins[:-1]
maxs = maxs[1:]

origin = 0
not_origin = 0

for p in p_list[:k]:
    if p_before < p:
        up += 1
    else:
        up=0
    p_before = p*1

    if p == p_list[k-1]:
        if up >= k-1:
            origin = 1
        else:
            not_origin = 1


for p,i in zip(p_list[k:], range(k,n)):
    if p_before < p:
        up += 1
    else:
        up=0
    p_before = p*1

    if up >= k-1:
        origin = 1
    else:
        if p_list[i-k] == mins[i-k]:
            if p_list[i] != maxs[i-k]:
                not_origin += 1
        else:
            not_origin += 1


print(origin + not_origin)


Fixed submission:
n,k = map(int,input().split())
p = tuple(map(int,input().split()))

class Seg_min():
    def __init__(self,x):
        #####単位元######
        self.ide_ele_min = 10**10
        self.func = min

        self.n = len(x)

        #num_max:n以上の最小の2のべき乗
        self.num_max =2**(self.n-1).bit_length()
        self.x = [self.ide_ele_min]*2*self.num_max

        for i,num in enumerate(x, self.num_max):
            self.x[i] = num
        for i in range(self.num_max-1,0,-1):
            self.x[i] = self.func(self.x[i<<1],self.x[(i<<1) + 1])

    def update(self,i,x):
        i += self.num_max
        self.x[i] = x
        while(x>0):
            i = i//2
            self.x[i] = self.func(self.x[i<<1],self.x[(i<<1) + 1])

    def query(self,i,j):
        res = self.ide_ele_min
        if i>=j:
            return res
        i += self.num_max
        j += self.num_max -1
        while(i<=j):
            if(i==j):
                res = self.func(res,self.x[i])
                break
            if(i&1):
                res = self.func(res,self.x[i])
                i += 1
            if(not j&1):
                res = self.func(res,self.x[j])
                j -= 1
            i = i>>1
            j = j>>1
        return res

class Seg_max():
    def __init__(self,x):
        #####単位元######
        self.ide_ele_min = 10**10 * -1
        self.func = max

        self.n = len(x)

        #num_max:n以上の最小の2のべき乗
        self.num_max =2**(self.n-1).bit_length()
        self.x = [self.ide_ele_min]*2*self.num_max

        for i,num in enumerate(x, self.num_max):
            self.x[i] = num
        for i in range(self.num_max-1,0,-1):
            self.x[i] = self.func(self.x[i<<1],self.x[(i<<1) + 1])

    def update(self,i,x):
        i += self.num_max
        self.x[i] = x
        while(x>0):
            i = i//2
            self.x[i] = self.func(self.x[i<<1],self.x[(i<<1) + 1])

    def query(self,i,j):
        res = self.ide_ele_min
        if i>=j:
            return res
        i += self.num_max
        j += self.num_max -1
        while(i<=j):
            if(i==j):
                res = self.func(res,self.x[i])
                break
            if(i&1):
                res = self.func(res,self.x[i])
                i += 1
            if(not j&1):
                res = self.func(res,self.x[j])
                j -= 1
            i = i>>1
            j = j>>1
        return res

seg_min = Seg_min(p)
seg_max = Seg_max(p)

natural = 0
ans = 0

head = 0
for i in range(1,n):
    if(p[i]<p[i-1]):
        head = i

    if(i-head >= k-1):
        natural = 1
        continue

    if(i==k-1):
        ans +=1
    if(i<k):
        continue
    ans += 1

    left = seg_min.query(i-k,i)
    right = seg_max.query(i-k+1,i+1)
    if(left==p[i-k])&(right==p[i]):
        ans -= 1

print(ans+natural)

Buggy python submission (verdict: Time Limit Exceeded):
n,k = map(int, input().split())
p_list = list(map(int, input().split()))

p_before = 200001
up = 0

mins = [0]*(n+1-k)
maxs = [0]*(n+1-k)

for i in range(n+1-k):
    temp = p_list[i:i+k]
    mins[i] = min(temp)
    maxs[i] = max(temp)

mins = mins[:-1]
maxs = maxs[1:]

origin = 0
not_origin = 0

for p in p_list[:k]:
    if p_before < p:
        up += 1
    else:
        up=0
    p_before = p*1

    if p == p_list[k-1]:
        if up >= k-1:
            origin = 1
        else:
            not_origin = 1


for p,i in zip(p_list[k:], range(k,n)):
    if p_before < p:
        up += 1
    else:
        up=0
    p_before = p*1

    if up >= k-1:
        origin = 1
    else:
        if p_list[i-k] == mins[i-k]:
            if p_list[i] != maxs[i-k]:
                not_origin += 1
        else:
            not_origin += 1


print(origin + not_origin)


Fixed submission:
n,k = map(int,input().split())
p = tuple(map(int,input().split()))

class Seg_min():
    def __init__(self,x):
        #####単位元######
        self.ide_ele_min = 10**10
        self.func = min

        self.n = len(x)

        #num_max:n以上の最小の2のべき乗
        self.num_max =2**(self.n-1).bit_length()
        self.x = [self.ide_ele_min]*2*self.num_max

        for i,num in enumerate(x, self.num_max):
            self.x[i] = num
        for i in range(self.num_max-1,0,-1):
            self.x[i] = self.func(self.x[i<<1],self.x[(i<<1) + 1])

    def update(self,i,x):
        i += self.num_max
        self.x[i] = x
        while(x>0):
            i = i//2
            self.x[i] = self.func(self.x[i<<1],self.x[(i<<1) + 1])

    def query(self,i,j):
        res = self.ide_ele_min
        if i>=j:
            return res
        i += self.num_max
        j += self.num_max -1
        while(i<=j):
            if(i==j):
                res = self.func(res,self.x[i])
                break
            if(i&1):
                res = self.func(res,self.x[i])
                i += 1
            if(not j&1):
                res = self.func(res,self.x[j])
                j -= 1
            i = i>>1
            j = j>>1
        return res

class Seg_max():
    def __init__(self,x):
        #####単位元######
        self.ide_ele_min = 10**10 * -1
        self.func = max

        self.n = len(x)

        #num_max:n以上の最小の2のべき乗
        self.num_max =2**(self.n-1).bit_length()
        self.x = [self.ide_ele_min]*2*self.num_max

        for i,num in enumerate(x, self.num_max):
            self.x[i] = num
        for i in range(self.num_max-1,0,-1):
            self.x[i] = self.func(self.x[i<<1],self.x[(i<<1) + 1])

    def update(self,i,x):
        i += self.num_max
        self.x[i] = x
        while(x>0):
            i = i//2
            self.x[i] = self.func(self.x[i<<1],self.x[(i<<1) + 1])

    def query(self,i,j):
        res = self.ide_ele_min
        if i>=j:
            return res
        i += self.num_max
        j += self.num_max -1
        while(i<=j):
            if(i==j):
                res = self.func(res,self.x[i])
                break
            if(i&1):
                res = self.func(res,self.x[i])
                i += 1
            if(not j&1):
                res = self.func(res,self.x[j])
                j -= 1
            i = i>>1
            j = j>>1
        return res

seg_min = Seg_min(p)
seg_max = Seg_max(p)

natural = 0
ans = 0

head = 0
for i in range(1,n):
    if(p[i]<p[i-1]):
        head = i

    if(i-head >= k-1):
        natural = 1
        continue

    if(i==k-1):
        ans +=1
    if(i<k):
        continue
    ans += 1

    left = seg_min.query(i-k,i)
    right = seg_max.query(i-k+1,i+1)
    if(left==p[i-k])&(right==p[i]):
        ans -= 1

print(ans+natural)

Buggy python submission (verdict: Runtime Error):
n,k = map(int, input().split())
p_list = list(map(int, input().split()))

p_before = 200001
up = 0

mins = [0]*(n-k)
maxs = [0]*(n-k)

for i in range(n+1-k):
    temp = p[i:i+k]
    mins[i] = min(temp)
    maxs[i] = max(temp)

mins = mins[:-1]
maxs = maxs[1:]

origin = 0
not_origin = 0

for p in p_list[:k]:
    if p_before < p:
        up += 1
    else:
        up=0
    p_before = p*1

    if p == p_list[k-1]:
        if up >= k-1:
            origin = 1
        else:
            not_origin = 1


for p,i in zip(p_list[k:], range(k,n)):
    if p_before < p:
        up += 1
    else:
        up=0
    p_before = p*1

    if up >= k-1:
        origin = 1
    else:
        if p_list[i-k] == mins[i-k]:
            if p_list[i] != maxs[i-k]:
                not_origin += 1
        else:
            not_origin += 1


print(origin + not_origin)


Fixed submission:
n,k = map(int,input().split())
p = tuple(map(int,input().split()))

class Seg_min():
    def __init__(self,x):
        #####単位元######
        self.ide_ele_min = 10**10
        self.func = min

        self.n = len(x)

        #num_max:n以上の最小の2のべき乗
        self.num_max =2**(self.n-1).bit_length()
        self.x = [self.ide_ele_min]*2*self.num_max

        for i,num in enumerate(x, self.num_max):
            self.x[i] = num
        for i in range(self.num_max-1,0,-1):
            self.x[i] = self.func(self.x[i<<1],self.x[(i<<1) + 1])

    def update(self,i,x):
        i += self.num_max
        self.x[i] = x
        while(x>0):
            i = i//2
            self.x[i] = self.func(self.x[i<<1],self.x[(i<<1) + 1])

    def query(self,i,j):
        res = self.ide_ele_min
        if i>=j:
            return res
        i += self.num_max
        j += self.num_max -1
        while(i<=j):
            if(i==j):
                res = self.func(res,self.x[i])
                break
            if(i&1):
                res = self.func(res,self.x[i])
                i += 1
            if(not j&1):
                res = self.func(res,self.x[j])
                j -= 1
            i = i>>1
            j = j>>1
        return res

class Seg_max():
    def __init__(self,x):
        #####単位元######
        self.ide_ele_min = 10**10 * -1
        self.func = max

        self.n = len(x)

        #num_max:n以上の最小の2のべき乗
        self.num_max =2**(self.n-1).bit_length()
        self.x = [self.ide_ele_min]*2*self.num_max

        for i,num in enumerate(x, self.num_max):
            self.x[i] = num
        for i in range(self.num_max-1,0,-1):
            self.x[i] = self.func(self.x[i<<1],self.x[(i<<1) + 1])

    def update(self,i,x):
        i += self.num_max
        self.x[i] = x
        while(x>0):
            i = i//2
            self.x[i] = self.func(self.x[i<<1],self.x[(i<<1) + 1])

    def query(self,i,j):
        res = self.ide_ele_min
        if i>=j:
            return res
        i += self.num_max
        j += self.num_max -1
        while(i<=j):
            if(i==j):
                res = self.func(res,self.x[i])
                break
            if(i&1):
                res = self.func(res,self.x[i])
                i += 1
            if(not j&1):
                res = self.func(res,self.x[j])
                j -= 1
            i = i>>1
            j = j>>1
        return res

seg_min = Seg_min(p)
seg_max = Seg_max(p)

natural = 0
ans = 0

head = 0
for i in range(1,n):
    if(p[i]<p[i-1]):
        head = i

    if(i-head >= k-1):
        natural = 1
        continue

    if(i==k-1):
        ans +=1
    if(i<k):
        continue
    ans += 1

    left = seg_min.query(i-k,i)
    right = seg_max.query(i-k+1,i+1)
    if(left==p[i-k])&(right==p[i]):
        ans -= 1

print(ans+natural)

Buggy python submission (verdict: Time Limit Exceeded):
n,k = map(int, input().split())
p_list = list(map(int, input().split()))

p_before = 200001
up = 0

origin = 0
not_origin = 0

for p in p_list[:k]:
    if p_before < p:
        up += 1
    else:
        up=0
    p_before = p*1

    if p == p_list[k-1]:
        if up >= k-1:
            origin = 1
        else:
            not_origin = 1


for p,i in zip(p_list[k:], range(k,n)):
    if p_before < p:
        up += 1
    else:
        up=0
    p_before = p*1

    if up >= k-1:
        origin = 1
    else:
        if p_list[i-k] == min(p_list[(i-k):i]):
            if p_list[i] != max(p_list[(i-k+1):(i+1)]):
                not_origin += 1
        else:
            not_origin += 1


print(origin + not_origin)


Fixed submission:
n,k = map(int,input().split())
p = tuple(map(int,input().split()))

class Seg_min():
    def __init__(self,x):
        #####単位元######
        self.ide_ele_min = 10**10
        self.func = min

        self.n = len(x)

        #num_max:n以上の最小の2のべき乗
        self.num_max =2**(self.n-1).bit_length()
        self.x = [self.ide_ele_min]*2*self.num_max

        for i,num in enumerate(x, self.num_max):
            self.x[i] = num
        for i in range(self.num_max-1,0,-1):
            self.x[i] = self.func(self.x[i<<1],self.x[(i<<1) + 1])

    def update(self,i,x):
        i += self.num_max
        self.x[i] = x
        while(x>0):
            i = i//2
            self.x[i] = self.func(self.x[i<<1],self.x[(i<<1) + 1])

    def query(self,i,j):
        res = self.ide_ele_min
        if i>=j:
            return res
        i += self.num_max
        j += self.num_max -1
        while(i<=j):
            if(i==j):
                res = self.func(res,self.x[i])
                break
            if(i&1):
                res = self.func(res,self.x[i])
                i += 1
            if(not j&1):
                res = self.func(res,self.x[j])
                j -= 1
            i = i>>1
            j = j>>1
        return res

class Seg_max():
    def __init__(self,x):
        #####単位元######
        self.ide_ele_min = 10**10 * -1
        self.func = max

        self.n = len(x)

        #num_max:n以上の最小の2のべき乗
        self.num_max =2**(self.n-1).bit_length()
        self.x = [self.ide_ele_min]*2*self.num_max

        for i,num in enumerate(x, self.num_max):
            self.x[i] = num
        for i in range(self.num_max-1,0,-1):
            self.x[i] = self.func(self.x[i<<1],self.x[(i<<1) + 1])

    def update(self,i,x):
        i += self.num_max
        self.x[i] = x
        while(x>0):
            i = i//2
            self.x[i] = self.func(self.x[i<<1],self.x[(i<<1) + 1])

    def query(self,i,j):
        res = self.ide_ele_min
        if i>=j:
            return res
        i += self.num_max
        j += self.num_max -1
        while(i<=j):
            if(i==j):
                res = self.func(res,self.x[i])
                break
            if(i&1):
                res = self.func(res,self.x[i])
                i += 1
            if(not j&1):
                res = self.func(res,self.x[j])
                j -= 1
            i = i>>1
            j = j>>1
        return res

seg_min = Seg_min(p)
seg_max = Seg_max(p)

natural = 0
ans = 0

head = 0
for i in range(1,n):
    if(p[i]<p[i-1]):
        head = i

    if(i-head >= k-1):
        natural = 1
        continue

    if(i==k-1):
        ans +=1
    if(i<k):
        continue
    ans += 1

    left = seg_min.query(i-k,i)
    right = seg_max.query(i-k+1,i+1)
    if(left==p[i-k])&(right==p[i]):
        ans -= 1

print(ans+natural)

Buggy python submission (verdict: Time Limit Exceeded):
import heapq

n,k = map(int, input().split())
p_list = list(map(int, input().split()))

p_before = 200001
up = 0

origin = 0
not_origin = 0

for p in p_list[:k]:
    if p_before < p:
        up += 1
    else:
        up=0
    p_before = p*1

    if p == p_list[k-1]:
        if up >= k-1:
            origin = 1
        else:
            not_origin = 1


for p,i in zip(p_list[k:], range(k,n)):
    if p_before < p:
        up += 1
    else:
        up=0
    p_before = p*1

    if up >= k-1:
        origin = 1
    else:
        if p_list[i-k] == min(p_list[(i-k):i]):
            if p_list[i] != max(p_list[(i-k+1):(i+1)]):
                not_origin += 1
        else:
            not_origin += 1


print(origin + not_origin)


Fixed submission:
n,k = map(int,input().split())
p = tuple(map(int,input().split()))

class Seg_min():
    def __init__(self,x):
        #####単位元######
        self.ide_ele_min = 10**10
        self.func = min

        self.n = len(x)

        #num_max:n以上の最小の2のべき乗
        self.num_max =2**(self.n-1).bit_length()
        self.x = [self.ide_ele_min]*2*self.num_max

        for i,num in enumerate(x, self.num_max):
            self.x[i] = num
        for i in range(self.num_max-1,0,-1):
            self.x[i] = self.func(self.x[i<<1],self.x[(i<<1) + 1])

    def update(self,i,x):
        i += self.num_max
        self.x[i] = x
        while(x>0):
            i = i//2
            self.x[i] = self.func(self.x[i<<1],self.x[(i<<1) + 1])

    def query(self,i,j):
        res = self.ide_ele_min
        if i>=j:
            return res
        i += self.num_max
        j += self.num_max -1
        while(i<=j):
            if(i==j):
                res = self.func(res,self.x[i])
                break
            if(i&1):
                res = self.func(res,self.x[i])
                i += 1
            if(not j&1):
                res = self.func(res,self.x[j])
                j -= 1
            i = i>>1
            j = j>>1
        return res

class Seg_max():
    def __init__(self,x):
        #####単位元######
        self.ide_ele_min = 10**10 * -1
        self.func = max

        self.n = len(x)

        #num_max:n以上の最小の2のべき乗
        self.num_max =2**(self.n-1).bit_length()
        self.x = [self.ide_ele_min]*2*self.num_max

        for i,num in enumerate(x, self.num_max):
            self.x[i] = num
        for i in range(self.num_max-1,0,-1):
            self.x[i] = self.func(self.x[i<<1],self.x[(i<<1) + 1])

    def update(self,i,x):
        i += self.num_max
        self.x[i] = x
        while(x>0):
            i = i//2
            self.x[i] = self.func(self.x[i<<1],self.x[(i<<1) + 1])

    def query(self,i,j):
        res = self.ide_ele_min
        if i>=j:
            return res
        i += self.num_max
        j += self.num_max -1
        while(i<=j):
            if(i==j):
                res = self.func(res,self.x[i])
                break
            if(i&1):
                res = self.func(res,self.x[i])
                i += 1
            if(not j&1):
                res = self.func(res,self.x[j])
                j -= 1
            i = i>>1
            j = j>>1
        return res

seg_min = Seg_min(p)
seg_max = Seg_max(p)

natural = 0
ans = 0

head = 0
for i in range(1,n):
    if(p[i]<p[i-1]):
        head = i

    if(i-head >= k-1):
        natural = 1
        continue

    if(i==k-1):
        ans +=1
    if(i<k):
        continue
    ans += 1

    left = seg_min.query(i-k,i)
    right = seg_max.query(i-k+1,i+1)
    if(left==p[i-k])&(right==p[i]):
        ans -= 1

print(ans+natural)