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

def slide_max(A, K):
    N = len(A)
    max_idx = [0] * N
    d = deque()
    for i in range(N):
        while d and d[0] <= i-K:
            d.popleft()
        while d and A[d[-1]] < A[i]:
            d.pop()
        d.append(i)
        max_idx[i] = d[0]
    return max_idx


def slide_min(A, K):
    N = len(A)
    min_idx = [0] * N
    d = deque()
    for i in range(N):
        while d and d[0] <= i-K:
            d.popleft()
        while d and A[d[-1]] > A[i]:
            d.pop()
        d.append(i)
        min_idx[i] = d[0]
    return min_idx

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

larger_than_left = [1] * N
for i in range(1, N):
  if A[i] < A[i-1]:
    larger_than_left[i] = 0

sorted_idx = set()
num = sum(larger_than_left[1:K])
if num == K-1:
  sorted_idx.add(0)
for i in range(1, N-K+1):
  num += larger_than_left[i+K-1] - larger_than_left[i]
  if num == K-1:
    sorted_idx.add(i)

max_idx = slide_max(A, K-1)
min_idx = slide_min(A, K-1)
ans = [] if 0 in sorted_idx else [0]
for i in range(1, N-K+1):
  if i in sorted_idx:
    continue
  left = A[i-1]
  right = A[i+K-1]
  M = A[max_idx[i+K-2]]
  m = A[min_idx[i+K-2]]
  if m < left or right < M:
    ans.append(i)

print(len(ans) + (len(sorted_idx)>0))