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:
def init(seg,init_val,n,num):
    #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]=min(seg[2*i+1],seg[2*i+2]) 
    return seg
    
def query(seg,p,q,n,num):
    if q<=p:
        return float("inf")
    p += num-1
    q += num-2
    res=float("inf")
    while q-p>1:
        if p&1 == 0:
            res = min(res,seg[p])
        if q&1 == 1:
            res = min(res,seg[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = min(res,seg[p])
    else:
        res = min(min(res,seg[p]),seg[q])
    return res

def init2(seg,init_val,n,num):
    #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] = max(seg[2*i+1],seg[2*i+2]) 
    return seg
    
def query2(seg,p,q,n,num):
    ide_ele = -float("inf")
    if q<=p:
        return ide_ele
    p += num-1
    q += num-2
    res=ide_ele
    while q-p>1:
        if p&1 == 0:
            res = max(res,seg[p])
        if q&1 == 1:
            res = max(res,seg[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = max(res,seg[p])
    else:
        res = max(max(res,seg[p]),seg[q])
    return res


def main():
    import sys
    input = sys.stdin.readline
    N,K = map(int,input().split())
    P = list(map(int,input().split()))
    
    num =2**(N-1).bit_length()
    seg1=[float("inf")]*2*num
    seg1 = init(seg1,P,N,num)
    seg2=[-float("inf")]*2*num
    seg2 = init2(seg2,P,N,num)
    
    ans = 1
    c = 0
    tmp = 0
    for i in range(N-1):
        if P[i]<P[i+1]:
            tmp += 1
        else:
            if tmp >= K-1:
                c += 1
            tmp = 0
    if tmp >= K-1:
        c += 1
        tmp = 0
        
        
    for i in range(N-K):
        m = query(seg1, i, i+K+1,N,num)
        M = query2(seg2, i, i+K+1,N,num)
        if P[i]!=m or P[i+K]!=M:
            ans += 1
    
    print(ans- max(0,c-1))
        
    
    
main()