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
N, K = map(int, input().split())
a = list(map(int, input().split()))
ans = 1
c = 0
d = 0
q = deque()
p = deque()
for i in range(K):
    if len(q) == 0:
        q.append(i)
    else:
        while len(q) > 0:
            if a[q[len(q)-1]] > a[i]:
                q.pop()
            else:
                q.append(i)
                break
        else:
            q.append(i)

    if len(p) == 0:
        p.append(i)
    else:
        while len(p) > 0:
            if a[p[len(p)-1]] < a[i]:
                p.pop()
            else:
                p.append(i)
                break
        else:
            p.append(i)
    if len(q) == K:
        c += 1

for i in range(K, N):
    if len(q) == 0:
        q.append(i)
    else:
        flag = 0
        while len(q) > 0:
            if a[q[len(q)-1]] > a[i]:
                q.pop()
                flag = 1
            else:
                q.append(i)
                break
        else:
            q.append(i)
        if q[0] == i-K:
            l = q.popleft()
        else:
            flag = 1

    if len(p) == 0:
        p.append(i)
    else:
        while len(p) > 0:
            if a[p[len(p)-1]] < a[i]:
                p.pop()
            else:
                p.append(i)
                break
        else:
            p.append(i)
        if a[p[0]] > a[i]:
            flag = 1

        if p[0] == i-K:
            l = p.popleft()



    if flag == 1:
        ans += 1
    if len(q) == K and flag == 1:
        c += 1

if c > 1:
    ans -= c-1
print(ans)