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 operator import lt, gt


def hoge(a, K, op):
    from collections import deque
    dq = deque()
    pop, popleft, append = dq.pop, dq.popleft, dq.append

    for i, v in zip(range(K), a):
        while dq and not op(a[dq[-1]], v):
            pop()
        append(i)

    yield a[dq[0]]

    for i in range(K, len(a)):
        while dq and not op(a[dq[-1]], a[i]):
            pop()
        append(i)
        if dq[0] == i-K:
            popleft()
        yield a[dq[0]]


N, K = map(int, input().split())
a = tuple(map(int, input().split()))

inv_flag = [0]*N

for i, (x, y) in enumerate(zip(a, a[1:]), start=1):
    inv_flag[i] = i if x > y else inv_flag[i-1]

min_coro = hoge(a, K, lt)
max_coro = hoge(a, K, gt)

prev_min, prev_max = next(min_coro), next(max_coro)
ans, flag = inv_flag[K-1] != 0, inv_flag[K-1] == 0

for l, r, x, y in zip(range(1, N), range(K, N), min_coro, max_coro):
    if inv_flag[l] == inv_flag[r]:
        flag = 1
    elif not (prev_min < x and prev_max < y):
        ans += 1

    prev_min, prev_max = x, y

print(ans + flag)