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 sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

import heapq

N, K = map(int, input().split())
P = list(map(int, input().split()))

Z = [0 for i in range(N)]
tmp = P[0]
count = 1
order = [0 for i in range(N)]
for i in range(1, N):
    if tmp < P[i]:
        count += 1
        if count >= K:
            order[i] = 1
    else:
        count = 1
    tmp = P[i]

hp = []
hm = []
heapq.heapify(hp)
heapq.heapify(hm)
used = [0 for i in range(N)]

for i in range(K):
    heapq.heappush(hp, P[i]) # 最小
    heapq.heappush(hm, -P[i]) # 最大

ans = 1
kaburi = [0 for i in range(N)]

for i in range(K, N):
    while used[hp[0]-1] == 1:
        heapq.heappop(hp)
    while used[-hm[0]-1] == 1:
        heapq.heappop(hm)

    if hp[0] == P[i-K] and -hm[0] < P[i]:
        kaburi[i] = 1
        pass
    else:
        ans += 1
    
    used[P[i-K]-1] = 1

    heapq.heappush(hp, P[i])
    heapq.heappush(hm, -P[i])

order_count = 0
for i in range(N):
    if kaburi[i] == 0 and order[i] == 1:
        order_count += 1

ans = N-K+1 - (sum(kaburi)+max(order_count-1, 0))
print(ans)