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:
import math


def main():
    N, K = map(int, input().split())
    P = list(map(int, input().split()))
    seq = 1
    for i in range(K-1):
        if P[i] < P[i+1]:
            seq += 1
        else:
            seq = 1
    has_orig = seq == K
    ln = int(math.log(K, 2))
    dp1 = [[0] * N for _ in range(ln+1)]
    dp2 = [[0] * N for _ in range(ln+1)]
    dp1[0] = P
    dp2[0] = P
    for k in range(ln):
        for i in range(N-2**k):
            dp1[k+1][i] = min(dp1[k][i], dp1[k][i+2**k])
            dp2[k+1][i] = max(dp2[k][i], dp2[k][i+2**k])
    rmq = [float("inf")] * (N-K+1)
    rMq = [0] * (N-K+1)
    for i in range(N-K+1):
        idx = i
        for k in range(ln+1)[::-1]:
            if K & (2**k):
                rmq[i] = min(rmq[i], dp1[k][idx])
                rMq[i] = max(rMq[i], dp2[k][idx])
                idx += 2**k
    ans = 1
    for i in range(N-K):
        if P[i+K-1] < P[i+K]:
            seq += 1
        else:
            seq = 1
        if seq >= K:
            if not has_orig:
                has_orig = True
                ans += 1
            continue
        if P[i] != rmq[i] or P[i+K] < rMq[i]:
            ans += 1
    print(ans)


if __name__ == "__main__":
    main()