Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
# K = 3
# a = [1,3,5,4,2]
# N = len(a)

N, K = map(int, input().split())
p = list(map(int, input().split()))

deq = deque()
min_val = [0] * (N - K + 1)
for i in range(N):
  while deq and p[deq[-1]] >= p[i]:
    deq.pop()
  deq.append(i)

  if i - K + 1 >= 0:
    min_val[i - K + 1] = p[deq[0]]
    if deq[0] == i - K + 1:
      deq.popleft()
#print(min_val)

deq = deque()
max_val = [0] * (N - K + 1)
for i in range(N):
  while deq and p[deq[-1]] <= p[i]:
    deq.pop()
  deq.append(i)

  if i - K + 1 >= 0:
    max_val[i - K + 1] = p[deq[0]]
    if deq[0] == i - K + 1:
      deq.popleft()
#print(max_val)

cnt = 0
preL = -1
prerange_min = -2
sortMatchCnt = 0
for i in range(N - K + 1):
  range_min = min_val[i]
  range_max = max_val[i]
  l = p[i]
  r = p[i + K - 1]

  sortMatchFlg = False
  if range_min == l and range_max == r:
    sortMatchFlg = p[i:i + K] == sorted(p[i:i + K])
    if sortMatchFlg:
      sortMatchCnt += 1                      

  if (preL == prerange_min and r == range_max) or sortMatchFlg:
    pass
  else:
    cnt += 1
  preL = l
  # preR = r
  prerange_min = range_min
  # prerange_max = range_max
if sortMatchCnt >= 1:
  print(cnt + 1)
else:
  print(cnt)


Fixed submission:
from collections import deque
import itertools
# K = 3
# a = [1,3,5,4,2]
# N = len(a)

N, K = map(int, input().split())
p = list(map(int, input().split()))

deq = deque()
min_val = [0] * (N - K + 1)
for i in range(N):
  while deq and p[deq[-1]] >= p[i]:
    deq.pop()
  deq.append(i)

  if i - K + 1 >= 0:
    min_val[i - K + 1] = p[deq[0]]
    if deq[0] == i - K + 1:
      deq.popleft()
#print(min_val)

deq = deque()
max_val = [0] * (N - K + 1)
for i in range(N):
  while deq and p[deq[-1]] <= p[i]:
    deq.pop()
  deq.append(i)

  if i - K + 1 >= 0:
    max_val[i - K + 1] = p[deq[0]]
    if deq[0] == i - K + 1:
      deq.popleft()
#print(max_val)

incr = [1 if x<y else 0 for x,y in zip(p, p[1:])]
incr_cum = [0] + list(itertools.accumulate(incr))
is_stable = [y-x==K-1 for x,y in zip(incr_cum,incr_cum[K-1:])]

cnt = 0
preL = -1
prerange_min = -2
sortMatchCnt = 0
for i in range(N - K + 1):
  range_min = min_val[i]
  range_max = max_val[i]
  l = p[i]
  r = p[i + K - 1]

  sortMatchFlg = False
  if is_stable[i]:
    sortMatchCnt += 1
    sortMatchFlg = True

  if (preL == prerange_min and r == range_max) or sortMatchFlg:
    pass
  else:
    cnt += 1
  preL = l
  # preR = r
  prerange_min = range_min
  # prerange_max = range_max
if sortMatchCnt >= 1:
  print(cnt + 1)
else:
  print(cnt)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
# K = 3
# a = [1,3,5,4,2]
# N = len(a)

N, K = map(int, input().split())
p = list(map(int, input().split()))

deq = deque()
min_val = [0] * (N - K + 1)
for i in range(N):
  while deq and p[deq[-1]] >= p[i]:
    deq.pop()
  deq.append(i)

  if i - K + 1 >= 0:
    min_val[i - K + 1] = p[deq[0]]
    if deq[0] == i - K + 1:
      deq.popleft()
#print(min_val)

deq = deque()
max_val = [0] * (N - K + 1)
for i in range(N):
  while deq and p[deq[-1]] <= p[i]:
    deq.pop()
  deq.append(i)

  if i - K + 1 >= 0:
    max_val[i - K + 1] = p[deq[0]]
    if deq[0] == i - K + 1:
      deq.popleft()
#print(max_val)

cnt = 0
preL = -1
prerange_min = -2
sortMatchCnt = 0
for i in range(N - K + 1):
  range_min = min_val[i]
  range_max = max_val[i]
  l = p[i]
  r = p[i + K - 1]

  sortMatchFlg = False
  if range_min == l and range_max == r:
    sortMatchFlg = p[i:i + K] == sorted(p[i:i + K])
    if sortMatchFlg:
      sortMatchCnt += 1                      

  if (preL == prerange_min and r == range_max) or sortMatchFlg:
    pass
  else:
    cnt += 1
  preL = l
  # preR = r
  prerange_min = range_min
  # prerange_max = range_max
if sortMatchCnt >= 1:
  print(cnt + 1)
else:
  print(cnt)

Fixed submission:
from collections import deque
import itertools
# K = 3
# a = [1,3,5,4,2]
# N = len(a)

N, K = map(int, input().split())
p = list(map(int, input().split()))

deq = deque()
min_val = [0] * (N - K + 1)
for i in range(N):
  while deq and p[deq[-1]] >= p[i]:
    deq.pop()
  deq.append(i)

  if i - K + 1 >= 0:
    min_val[i - K + 1] = p[deq[0]]
    if deq[0] == i - K + 1:
      deq.popleft()
#print(min_val)

deq = deque()
max_val = [0] * (N - K + 1)
for i in range(N):
  while deq and p[deq[-1]] <= p[i]:
    deq.pop()
  deq.append(i)

  if i - K + 1 >= 0:
    max_val[i - K + 1] = p[deq[0]]
    if deq[0] == i - K + 1:
      deq.popleft()
#print(max_val)

incr = [1 if x<y else 0 for x,y in zip(p, p[1:])]
incr_cum = [0] + list(itertools.accumulate(incr))
is_stable = [y-x==K-1 for x,y in zip(incr_cum,incr_cum[K-1:])]

cnt = 0
preL = -1
prerange_min = -2
sortMatchCnt = 0
for i in range(N - K + 1):
  range_min = min_val[i]
  range_max = max_val[i]
  l = p[i]
  r = p[i + K - 1]

  sortMatchFlg = False
  if is_stable[i]:
    sortMatchCnt += 1
    sortMatchFlg = True

  if (preL == prerange_min and r == range_max) or sortMatchFlg:
    pass
  else:
    cnt += 1
  preL = l
  # preR = r
  prerange_min = range_min
  # prerange_max = range_max
if sortMatchCnt >= 1:
  print(cnt + 1)
else:
  print(cnt)

Buggy python submission (verdict: Time Limit Exceeded):
N, K = map(int, input().split())
p = list(map(int, input().split()))
cnt = 0
preL = -1
prerange_min = -2
sortMatchCnt = 0
for i in range(N - K + 1):
  hea = set(p[i:i + K])
  heap = sorted(hea)
  range_min = heap[0]
  range_max = heap[-1]
  l = p[i]
  r = p[i + K - 1]

  sortMatchFlg = False
  if range_min == l and range_max == r:
    sortMatchFlg = p[i:i + K] == heap
    if sortMatchFlg:
      sortMatchCnt += 1                      

  if (preL == prerange_min and r == range_max) or sortMatchFlg:
    pass
  else:
    cnt += 1
  preL = l
  # preR = r
  prerange_min = range_min
  # prerange_max = range_max
if sortMatchCnt >= 1:
  print(cnt + 1)
else:
  print(cnt)


Fixed submission:
from collections import deque
import itertools
# K = 3
# a = [1,3,5,4,2]
# N = len(a)

N, K = map(int, input().split())
p = list(map(int, input().split()))

deq = deque()
min_val = [0] * (N - K + 1)
for i in range(N):
  while deq and p[deq[-1]] >= p[i]:
    deq.pop()
  deq.append(i)

  if i - K + 1 >= 0:
    min_val[i - K + 1] = p[deq[0]]
    if deq[0] == i - K + 1:
      deq.popleft()
#print(min_val)

deq = deque()
max_val = [0] * (N - K + 1)
for i in range(N):
  while deq and p[deq[-1]] <= p[i]:
    deq.pop()
  deq.append(i)

  if i - K + 1 >= 0:
    max_val[i - K + 1] = p[deq[0]]
    if deq[0] == i - K + 1:
      deq.popleft()
#print(max_val)

incr = [1 if x<y else 0 for x,y in zip(p, p[1:])]
incr_cum = [0] + list(itertools.accumulate(incr))
is_stable = [y-x==K-1 for x,y in zip(incr_cum,incr_cum[K-1:])]

cnt = 0
preL = -1
prerange_min = -2
sortMatchCnt = 0
for i in range(N - K + 1):
  range_min = min_val[i]
  range_max = max_val[i]
  l = p[i]
  r = p[i + K - 1]

  sortMatchFlg = False
  if is_stable[i]:
    sortMatchCnt += 1
    sortMatchFlg = True

  if (preL == prerange_min and r == range_max) or sortMatchFlg:
    pass
  else:
    cnt += 1
  preL = l
  # preR = r
  prerange_min = range_min
  # prerange_max = range_max
if sortMatchCnt >= 1:
  print(cnt + 1)
else:
  print(cnt)

Buggy python submission (verdict: Time Limit Exceeded):
import heapq
N, K = map(int, input().split())
p = list(map(int, input().split()))
cnt = 0
preL = -1
prerange_min = -2
sortMatchCnt = 0
for i in range(N - K + 1):
  range_min = min(p[i:i + K])
  range_max = max(p[i:i + K])
  l = p[i]
  r = p[i + K - 1]

  sortMatchFlg = False
  if range_min == l and range_max == r:
    sortMatchFlg = p[i:i + K] == sorted(p[i:i + K])
    if sortMatchFlg:
      sortMatchCnt += 1                      

  if (preL == prerange_min and r == range_max) or sortMatchFlg:
    pass
  else:
    cnt += 1
  preL = l
  # preR = r
  prerange_min = range_min
  # prerange_max = range_max
if sortMatchCnt >= 1:
  print(cnt + 1)
else:
  print(cnt)


Fixed submission:
from collections import deque
import itertools
# K = 3
# a = [1,3,5,4,2]
# N = len(a)

N, K = map(int, input().split())
p = list(map(int, input().split()))

deq = deque()
min_val = [0] * (N - K + 1)
for i in range(N):
  while deq and p[deq[-1]] >= p[i]:
    deq.pop()
  deq.append(i)

  if i - K + 1 >= 0:
    min_val[i - K + 1] = p[deq[0]]
    if deq[0] == i - K + 1:
      deq.popleft()
#print(min_val)

deq = deque()
max_val = [0] * (N - K + 1)
for i in range(N):
  while deq and p[deq[-1]] <= p[i]:
    deq.pop()
  deq.append(i)

  if i - K + 1 >= 0:
    max_val[i - K + 1] = p[deq[0]]
    if deq[0] == i - K + 1:
      deq.popleft()
#print(max_val)

incr = [1 if x<y else 0 for x,y in zip(p, p[1:])]
incr_cum = [0] + list(itertools.accumulate(incr))
is_stable = [y-x==K-1 for x,y in zip(incr_cum,incr_cum[K-1:])]

cnt = 0
preL = -1
prerange_min = -2
sortMatchCnt = 0
for i in range(N - K + 1):
  range_min = min_val[i]
  range_max = max_val[i]
  l = p[i]
  r = p[i + K - 1]

  sortMatchFlg = False
  if is_stable[i]:
    sortMatchCnt += 1
    sortMatchFlg = True

  if (preL == prerange_min and r == range_max) or sortMatchFlg:
    pass
  else:
    cnt += 1
  preL = l
  # preR = r
  prerange_min = range_min
  # prerange_max = range_max
if sortMatchCnt >= 1:
  print(cnt + 1)
else:
  print(cnt)