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:
N, K = map(int, input().split())
# セグメント木(min, max)
N += 1
N0 = 2**(N-1).bit_length()
INF = float('inf')
minST = [INF]*(2*N0)
def update_min(k, x):
  k += N0-1
  minST[k] = x
  while k >= 0:
    k = (k - 1) // 2
    minST[k] = min(minST[2*k+1], minST[2*k+2])
def query_min(l, r):
  L = l + N0; R = r + N0
  s = INF
  while L < R:
    if R & 1:
      R -= 1
      s = min(s, minST[R-1])
    if L & 1:
      s = min(s, minST[L-1])
      L += 1
    L >>= 1; R >>= 1
  return s

MINF = float('-inf')
maxST = [MINF]*(2*N0)
def update_max(k, x):
  k += N0-1
  maxST[k] = x
  while k >= 0:
    k = (k - 1) // 2
    maxST[k] = max(maxST[2*k+1], maxST[2*k+2])

def query_max(l, r):
  L = l + N0; R = r + N0
  s = MINF
  while L < R:
    if R & 1:
      R -= 1
      s = max(s, maxST[R-1])
    if L & 1:
      s = max(s, maxST[L-1])
      L += 1
    L >>= 1; R >>= 1
  return s

Ps = list(map(int, input().split())) + [-1]
sorted_lens = []
tmp = 0
prev = -1
for i, p in enumerate(Ps):
  update_min(i, p)
  update_max(i, p)
  if prev > p:
    tmp = 0
  tmp += 1
  sorted_lens.append(tmp)
  prev = p

ans = N-K
flag = False
for i in range(N-K):
  smin = query_min(i, i+K+1)
  smax = query_max(i, i+K+1)
  if (smin == Ps[i] and smax == Ps[i+K]) or (flag and sorted_lens[i+K] >= K):
    ans -= 1
  if sorted_lens[i+K-1] == K:
    flag = True

print(ans)