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())
P=list(map(int,input().split()))

LIS=[1 for i in range(0,N)]
s=0
t=1
while N>t:
    if P[t]>=P[t-1]:
        t+=1
        if t==N:
            ans=N-s
            while t>s:
                LIS[s]=ans
                s+=1
                ans-=1
    else:
        ans=t-s
        while t>s:
            LIS[s]=ans
            s+=1
            ans-=1
        t+=1

nochange=set([])
for i in range(0,N-K+1):
    if LIS[i]>=K:
        nochange.add(i)

n=N
#セグメント木
#####segfunc######
def segfunc(x,y):
    return (min(x[0],y[0]),max(x[1],y[1]))

def init(init_val):
    #set_val
    for i in range(n):
        seg[i+num-1]=init_val[i]
    #built
    for i in range(num-2,-1,-1) :
        seg[i]=segfunc(seg[2*i+1],seg[2*i+2])

def update(k,x):
    k += num-1
    seg[k] = x
    while k:
        k = (k-1)//2
        seg[k] = segfunc(seg[k*2+1],seg[k*2+2])

def query(p,q):
    if q<=p:
        return ide_ele
    p += num-1
    q += num-2
    res=ide_ele
    while q-p>1:
        if p&1 == 0:
            res = segfunc(res,seg[p])
        if q&1 == 1:
            res = segfunc(res,seg[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = segfunc(res,seg[p])
    else:
        res = segfunc(segfunc(res,seg[p]),seg[q])
    return res

#####単位元######
ide_ele =(10**20,0)

#num:n以上の最小の2のべき乗
num =2**(n-1).bit_length()
seg=[ide_ele]*2*num
PP=[(P[i],P[i]) for i in range(0,N)]
init(PP)
ans=[]
if 0 not in nochange:
    ans.append(0)
for i in range(1,N-K+1):
    if i in nochange:
        continue
    else:
        M=query(i,i+K)[1]
        m=query(i-1,i-1+K)[0]
        if m==P[i-1] and M==P[i+K-1]:
            continue
        else:
            ans.append(i)

if nochange:
    print(len(ans)+1)
else:
    print(len(ans))