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

n,k=map(int,input().split())
p=list(map(int,input().split()))+[1000000]

p1=[0]*(n)
pmin=[0]*(n+1)
pmax=[0]*(n+1)

cnt=0

for i in range(n-1):
  if p[i]<p[i+1]:
    cnt+=1
  else:
    cnt=0
  p1[i+1]=cnt

d=deque()
d.append(0)

for i in range(1,k+1):
  if p[d[-1]]<p[i]:
    d.append(i)
  else:
    try:
      while p[d[-1]]>p[i]:
        d.pop()
    except:
      pass
    d.append(i)
pmin[k]=p[d[0]]

for i in range(k+1,n):
  if d[0]==i-(k+1):
    d.popleft()
  if p[d[-1]]<p[i]:
    d.append(i)
  else:
    try:
      while p[d[-1]]>p[i]:
        d.pop()
    except:
      pass
    d.append(i)
  pmin[i]=p[d[0]]


dd=deque()
dd.append(0)

for i in range(1,k+1):
  if p[dd[-1]]>p[i]:
    dd.append(i)
  else:
    try:
      while p[dd[-1]]<p[i]:
        dd.pop()
    except:
      pass
    dd.append(i)
pmax[k]=p[dd[0]]

for i in range(k+1,n):
  if dd[0]==i-(k+1):
    dd.popleft()
  if p[dd[-1]]>p[i]:
    dd.append(i)
  else:
    try:
      while p[dd[-1]]<p[i]:
        dd.pop()
    except:
      pass
    dd.append(i)
  pmax[i]=p[dd[0]]

ans=n-k+1
f=1
ff=[0]*n
for i in range(n):
  if p1[i]>=k-1:
    ff[i]=1
    if f==0:
      ans-=1
    else:
      f=0

for i in range(n-k):
  if p[i]==pmin[i+k] and p[i+k]==pmax[i+k] and ff[i+k]==0:
    ans-=1

print(ans)