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 heapq import heapify, heappop, heappush

n, k = list(map(int, input().split()))
ppp = list(map(int, input().split()))

increases = [int(p1 < p2) for p1, p2 in zip(ppp, ppp[1:])]
h = k - 1
tmp = sum(increases[:h])
duplicated = [0] * n
first_ascending = True
for i, q in enumerate(increases[h:], start=h):
    tmp += q - increases[i - h]
    if tmp == h:
        if first_ascending:
            first_ascending = False
        else:
            duplicated[i + 1] = 1

state = [1] * k + [0] * (n - k)
ans = 1
minq = ppp[:k]
maxq = [-p for p in ppp[:k]]
heapify(minq)
heapify(maxq)

# print(duplicated)

for i, p in enumerate(ppp[k:], start=k):
    l = ppp[i - k]

    if l == minq[0] and p > -maxq[0]:
        pass
    elif duplicated[i] == 1:
        pass
    else:
        ans += 1
    state[l] = 2
    state[p] = 1
    while state[minq[0]] == 2:
        heappop(minq)
    while state[-maxq[0]] == 2:
        heappop(maxq)
    heappush(minq, p)
    heappush(maxq, -p)
    # print(i, p, ans)
    # print(state)
    # print(minq)
    # print(maxq)

print(ans)