Problem: 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.

Constraints

* 2 \leq N \leq 200000
* 2 \leq K \leq N
* 0 \leq P_i \leq N-1
* P_0,P_1,\cdots,P_{N-1} are all different.
* All values in input are integers.

Input

Input is given from Standard Input in the following format:


N K
P_0 P_1 \cdots P_{N-1}


Output

Print the number of permutations that can be produced as P after the operation.

Examples

Input

5 3
0 2 1 4 3


Output

2


Input

4 4
0 1 2 3


Output

1


Input

10 4
2 0 1 3 7 5 4 6 8 9


Output

6

Solution (in PYTHON3):

Solution:
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)