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()))
INF = float('inf')
num = 2**(N-1).bit_length()
segmin = [INF] * num*2
segmax = [-INF] * num*2
for i in range(N):
    segmin[num + i - 1] = P[i]
    segmax[num + i - 1] = P[i]
for i in range(num-2, -1, -1):
    segmin[i] = min(segmin[2*i+1], segmin[2*i+2])
    segmax[i] = max(segmax[2*i+1], segmax[2*i+2])

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

ans = 1
for i in range(N-K):
    if not (P[i] < query(segmin, min, INF, i+1, i+K) and P[i+K] > query(segmax, max, -INF, i+1, i+K)):
        ans += 1

# 昇順にならんでいるケース
combo = 0
nord = 0
for i in range(1,N):
    if P[i] > P[i-1]:
        combo += 1
    else:
        combo = 0
    if combo == K-1:
        nord += 1

print(ans - max(0, nord-1))