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 = [float('inf')]+list(map(int,input().split()))+[float('inf')]

A = [0]*N
B = [0]*(N+2)
hoge = 1
for i in range(1,N):
    if P[i] < P[i+1]:
        hoge += 1
    else:
        hoge = 1
    if hoge >= K:
        B[i-K+2] = 1
    
for i in range(1,N+1):
    A[P[i]] = i
minL,minR,maxL,maxR = [i-1 for i in range(N+2)],[i+1 for i in range(N+2)],[i-1 for i in range(N+2)],[i+1 for i in range(N+2)]
for i in range(N):
    m = A[i]
    x,y = maxL[m],maxR[m]
    maxL[y] = x
    maxR[x] = y
P[0],P[-1] = -1,-1

for i in range(N-1,-1,-1):
    m = A[i]
    x,y = minL[m],minR[m]
    minL[y] = x
    minR[x] = y
ans = 1
for i in range(1,N-K+1):
    # print(i)
    L,R = i,i+K
    # print(i,P[L],P[R],minR[L],maxL[R],B[i+1])
    if B[i+1] == 0 and (minR[L] <= R or maxL[R] >= L):
        # print(i)
        ans += 1
# print(minR[1:-1])
# print(maxL[1:-1])
if sum(B) and B[1] == 0:
    ans += 1
# print(B)
print(ans)