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 MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]

n,k=MI()
a=LI()

def slidmin(a,k):
    n=len(a)
    b=[0 for i in range(n-k+1)]
    q=deque()
    for i in range(k):
        while q and a[q[-1]]>=a[i]:
            q.pop()
        q.append(i)
    b[0]=a[q[0]]
    s=len(q)
    for i in range(k,n):
        while q and a[q[-1]]>=a[i]:
            q.pop()
            s-=1
        q.append(i)
        s+=1
        if q[0]<=i-k:
            q.popleft()
            s-=1
        b[i-k+1]=a[q[0]]
    return b

m=slidmin(a,k)
M=[-i for i in slidmin([-i for i in a],k)]
ans=1
p=-1
c=0
for i in range(k):
    if p<a[i]:
        c+=1
    else:
        c=1
    p=a[i]
fl=True if c==k else False

for i in range(n-k):
    if p<a[i+k]:
        c+=1
    else:
        c=1
    p=a[i+k]
    
    inc=1
    if c==k:
        if fl:
            inc=0
        fl=True
    if a[i]==m[i] and a[i+k]==M[i+1]:
        inc=0
    ans+=inc
print(ans)