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 sys import stdin
from collections import deque

N, K = [int(x) for x in stdin.readline().rstrip().split()]
P = [int(x) for x in stdin.readline().rstrip().split()]

ans = N - K + 1

D = deque([x for x in P[:K]])
oc = 0
ordered_twice = False

for i in range(len(D) - 1):
    if D[i] <= D[i + 1]:
        oc += 1

Q = deque([])
Q_min = []
Q_max = []

for i in range(N):
    while len(Q) > 0 and P[Q[len(Q) - 1]] >= P[i]:
        Q.pop()
    Q.append(i)
    if Q[len(Q) - 1] >= K - 1:
        Q_min.append(P[Q[0]])
        if Q[0] == i + 1 - K:
            Q.popleft()

PP = [-x for x in P]
Q = deque([])

for i in range(N):
    while len(Q) > 0 and PP[Q[len(Q) - 1]] >= PP[i]:
        Q.pop()
    Q.append(i)
    if Q[len(Q) - 1] >= K - 1:
        Q_max.append(-PP[Q[0]])
        if Q[0] == i + 1 - K:
            Q.popleft()

for i in range(N - K + 1):
    if i > 0:
        D.popleft()
        D.append(P[i + K - 1])
        if P[i - 1] <= D[0]:
            oc -= 1
        if D[K - 2] <= D[K - 1]:
            oc += 1

        if (Q_min[i - 1] == P[i - 1] and Q_max[i] == D[-1]) or (oc == K - 1 and ordered_twice):
            ans -= 1

    if oc == K - 1:
        ordered_twice = True

print(ans)