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 collections import Counter, deque
N, K = map(int, input().split())
P = list(map(int, input().split()))
ans = N - K + 1


# 変化しないものを数える
LIS = [-1] * N
LIS[-1] = 1
LIS_MIN_NOW = P[-1]
for i in reversed(range(N - 1)):
    p = P[i]
    if p < LIS_MIN_NOW:
        LIS_MIN_NOW = p
        LIS[i] = LIS[i + 1] + 1
    else:
        LIS_MIN_NOW = p
        LIS[i] = 1
LIS = LIS[:N - K + 1]


def slide_min(A, K):
    deq, ret = deque([]), []
    for k in range(len(A)):
        while deq and A[deq[-1]] >= A[k]:
            deq.pop()
        deq.append(k)

        if k < K - 1:
            continue

        if deq[0] + K <= k:
            deq.popleft()
        ret.append(A[deq[0]])

    return ret


# スライド最小値・最大値を計算
MIN = slide_min(P, K)
MAX = list(map(lambda x: -x, slide_min(list(map(lambda x: -x, P)), K)))


for i in range(N - K + 1):
    flg = False
    if LIS[i] >= K:
        flg = True

    if (i + 1 < N - K + 1) and (P[i] == MIN[i]) and (P[i + K] == MAX[i + 1]):
        flg = True

    ans -= flg

if len([l for l in LIS if l >= K]):
    ans += 1
print(ans)