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]


# スライド最小値を計算
slide_min = deque([])
MIN = []
for k in range(N):
    while slide_min and P[slide_min[-1]] >= P[k]:
        slide_min.pop()
    slide_min.append(k)

    if k < K - 1:
        continue

    if slide_min[0] + K <= k:
        slide_min.popleft()
    MIN.append(P[slide_min[0]])


# スライド最大値を計算
slide_max = deque([])
MAX = []
for k in range(N):
    while slide_max and P[slide_max[-1]] <= P[k]:
        slide_max.pop()
    slide_max.append(k)

    if k < K - 1:
        continue

    if slide_max[0] + K <= k:
        slide_max.popleft()
    MAX.append(P[slide_max[0]])


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)