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 deque

def sliding_minima(a, k):
    dq = deque()
    l = r = 0
    ret = []
    for i, item in enumerate(a):
        while(dq and a[dq[-1]] >= a[i]):
            dq.pop()
        dq.append(i)
        if i < k - 1:
            continue
        if dq[0] == i - k:
            dq.popleft()
        ret.append(a[dq[0]])
    return ret

def sliding_maxima(a, k):
    dq = deque()
    l = r = 0
    ret = []
    for i, item in enumerate(a):
        while(dq and a[dq[-1]] <= a[i]):
            dq.pop()
        dq.append(i)
        if i < k - 1:
            continue
        if dq[0] == i - k:
            dq.popleft()
        ret.append(a[dq[0]])
    return ret

def is_increasing(a, k):
    increasing = [0] * len(a)
    for i, (a1, a2) in enumerate(zip(a, a[1:])):
        if a1 < a2:
            increasing[i+1] = 1
    ret = [0] * (len(a) - k + 1)
    val = sum(increasing[1:k])
    if val == k-1:
        ret[0] = 1
    for i in range(len(a) - k):
        val += increasing[i + k]
        val -= increasing[i + 1]
        if val == k-1:
            ret[i+1] = 1
        else:
            ret[i+1] = 0
    return ret

n, k = [int(item) for item in input().split()]
a = [int(item) for item in input().split()]

minima = sliding_minima(a, k)
maxima = sliding_maxima(a, k)
increasing = is_increasing(a, k)

ans = n - k + 1
if increasing[0]:
    ans -= 1
for l, r, minima, maxima, inc in zip(a, a[k:], minima[1:], maxima, increasing[1:]):
    if (l < minima and r > maxima) or inc:
        ans -= 1
if sum(increasing) > 0:
    ans += 1
print(ans)