output_description: Print the number of permutations that can be produced as P after the
  operation.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      N K
      P_0 P_1 \cdots P_{N-1}
attempt: from heapq import heapify, heappush, heappop
  
  
  def solve():
      N, K = map(int, input().split())
      Ps = list(map(int, input().split()))
  
      ans = N - K + 1
  
      numAsc = 0
      num = 0
      P0 = -1
      for P in Ps + [-1]:
          if P0 < P:
              num += 1
          else:
              if num >= K:
                  numAsc += num - K + 1
              num = 1
          P0 = P
      if numAsc > 0:
          ans -= numAsc - 1
  
      if K > 2:
          mins = [N] * N
          P = min(Ps[: K + 1])
          mins[0] = P
          PQ = [(P, i) for i, P in enumerate(Ps[: K + 1])]
          heapify(PQ)
          for i in range(K + 1, N):
              heappush(PQ, (Ps[i], i))
              while True:
                  P, pos = heappop(PQ)
                  if i - K <= pos:
                      mins[i - K] = P
                      heappush(PQ, (P, pos))
                      break
  
          maxs = [-1] * N
          P = max(Ps[: K + 1])
          maxs[0] = P
          PQ = [(-P, i) for i, P in enumerate(Ps[: K + 1])]
          heapify(PQ)
          for i in range(K + 1, N):
              heappush(PQ, (-Ps[i], i))
              while True:
                  P, pos = heappop(PQ)
                  if i - K <= pos:
                      maxs[i - K] = -P
                      heappush(PQ, (P, pos))
                      break
  
          isSorteds = [False] * N
          num = 0
          P0 = -1
          for i, P in enumerate(Ps + [-1]):
              if P0 < P:
                  num += 1
                  if num >= K - 1:
                      isSorteds[i - K + 1] = True  ###
              else:
                  if num >= K:
                      numAsc += num - K + 1
                  num = 1
              P0 = P
  
          for i in range(N - K):
              L, R = Ps[i], Ps[i + K]
              minK, maxK = mins[i], maxs[i]
              if L == minK and R == maxK and not isSorteds[i]:
                  ans -= 1
  
      print(ans)
  
  
  solve()
  
problem_description: Statement
  
  Snuke has a permutation (P_0,P_1,\cdots,P_{N-1}) of (0,1,\cdots,N-1).
  
  Now, he will perform the following operation **exactly once** :
  
    * Choose K consecutive elements in P and sort them in ascending order.
  
  Find the number of permutations that can be produced as P after the operation.
samples: [{"input": "5 3\n    0 2 1 4 3", "output": "2\n    \n\nTwo permutations can be produced as P after the operation: (0,1,2,4,3) and\n(0,2,1,3,4).\n\n* * *"}, {"input": "4 4\n    0 1 2 3", "output": "1\n    \n\n* * *"}, {"input": "10 4\n    2 0 1 3 7 5 4 6 8 9", "output": "6"}]