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:
import heapq
from collections import deque, Counter
N, K = map(int, input().split())
P = list(map(int, input().split()))
#ans = []
q = deque()
q_idx = []
L = []
for i, p in enumerate(P):
    while q and p <= q[-1][1]:
        idx, _ = q.pop()
        heapq.heappush(q_idx, idx)
    q.append((i, p))
    #print(q, q_idx)
    L.append(q_idx[0] if q_idx else -1)
    #ans.append(q[0][1])
    if q and q[0][0] <= i+1-K:
        idx, _ = q.popleft()
    if q_idx and q_idx[0] <= i+1-K:
        heapq.heappop(q_idx)
L = L[K-1:]

P = [-p for p in P]
P.reverse()
q = deque()
q_idx = []
R = []
for i, p in enumerate(P):
    while q and p <= q[-1][1]:
        idx, _ = q.pop()
        heapq.heappush(q_idx, idx)
    q.append((i, p))
    #print(q, q_idx)
    R.append(N - 1 - q_idx[0] if q_idx else -1)
    #ans.append(q[0][1])
    if q and q[0][0] <= i+1-K:
        idx, _ = q.popleft()
    if q_idx and q_idx[0] <= i+1-K:
        heapq.heappop(q_idx)
R = R[K-1:]
R.reverse()

#for l, r in zip(L, R):
print(len(Counter(zip(L, R))))