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:
N, K = map(int, input().split())
P = list(map(int, input().split()))

# N:  処理する区間の長さ
N0 = 2**(N-1).bit_length()
INF = 10**6
seg_min = [INF]*(2*N0)
seg_max = [-INF]*(2*N0)


def update(index, value):
    index += N0 - 1
    seg_min[index] = value
    seg_max[index] = value
    while index > 0:
        index = (index - 1) // 2
        seg_min[index] = min(seg_min[index * 2 + 1], seg_min[index * 2 + 2])
        seg_max[index] = max(seg_max[index * 2 + 1], seg_max[index * 2 + 2])


def query(first, last):
    first += N0 - 1
    last += N0 - 1
    ret_min = INF
    ret_max = -INF
    while first <= last:
        if not first & 1:
            ret_min = min(ret_min, seg_min[first])
            ret_max = max(ret_max, seg_max[first])
        if last & 1:
            ret_min = min(ret_min, seg_min[last])
            ret_max = max(ret_max, seg_max[last])
        first = first // 2
        last = last // 2 - 1
    return ret_min, ret_max


for i in range(N):
    update(i, P[i])

ans = 1
for i in range(1, N - K + 1):
    s, b = query(i-1, K+i-1)
    # print(s, b, P[i - 1], P[K + i - 1])
    if s != P[i-1] or b != P[K+i-1]:
        ans += 1

kaburi = 0
cnt = 0
for i in range(1, N):
    if P[i-1] < P[i]:
        cnt += 1
    else:
        cnt = 0
    if cnt == K-1:
        kaburi += 1
kaburi = max(0, kaburi - 1)

print(ans - kaburi)