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, heappush, heappop

def solve():
    N, K = map(int, input().split())
    Ps = list(map(int, input().split()))

    ans = N - K + 1

    numAsc = 0
    num = 0
    P0 = -1
    for P in (Ps+[-1]):
        if P0 < P:
            num += 1
        else:
            if num >= K:
                numAsc += num-K+1
            num = 1
        P0 = P
    if numAsc > 0:
        ans -= numAsc - 1

    if K > 2:
        mins = [N] * N
        P = min(Ps[:K+1])
        mins[0] = P
        PQ = [(P, i) for i, P in enumerate(Ps[:K+1])]
        heapify(PQ)
        for i in range(K+1, N):
            heappush(PQ, (Ps[i], i))
            while True:
                P, pos = heappop(PQ)
                if i-K <= pos:
                    mins[i-K] = P
                    heappush(PQ, (P, pos))
                    break

        maxs = [-1] * N
        P = max(Ps[:K+1])
        maxs[0] = P
        PQ = [(-P, i) for i, P in enumerate(Ps[:K+1])]
        heapify(PQ)
        for i in range(K+1, N):
            heappush(PQ, (-Ps[i], i))
            while True:
                P, pos = heappop(PQ)
                if i-K <= pos:
                    maxs[i-K] = -P
                    heappush(PQ, (P, pos))
                    break

        isSorteds = [False] * N
        num = 0
        P0 = -1
        for i, P in enumerate(Ps+[-1]):
            if P0 < P:
                num += 1
                if num >= K-1:
                    isSorteds[i-K+1] = True  ###
            else:
                if num >= K:
                    numAsc += num-K+1
                num = 1
            P0 = P

        for i in range(N-K):
            L, R = Ps[i], Ps[i+K]
            minK, maxK = mins[i], maxs[i]
            if L == minK and R == maxK and not isSorteds[i]:
                ans -= 1

    print(ans)


solve()