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

input = sys.stdin.readline

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

def slide_min(P,K):
	q = deque()
	q.append(0)
	slide_minl = []
	for i in range(1,len(P)):
		while P[i]<P[q[-1]]:
			q.pop()
			if len(q)==0: break
		q.append(i)

		if i>=K-1:
			slide_minl.append(P[q[0]])
			if q[0]<=i-K+1:
				q.popleft()

	return slide_minl

def slide_max(P,K):
	q = deque()
	q.append(0)
	slide_maxl = []
	for i in range(1,len(P)):
		while P[i]>P[q[-1]]:
			q.pop()
			if len(q)==0: break
		q.append(i)

		if i>=K-1:
			slide_maxl.append(P[q[0]])
			if q[0]<=i-K+1:
				q.popleft()

	return slide_maxl

minl = slide_min(P,K)
maxl = slide_max(P,K)

if N==K:
	ans = 1
else:
	ans = 1
	for i in range(K,N):
		last = P[i]
		pre = P[i-K]
		if pre!=minl[i-K] or last!=maxl[i-K+1]:
			ans += 1
			# print(i)

	count = 0
	i = 0
	while i<N-1:
		upnum = 0
		while P[i]<P[i+1]:
			upnum += 1
			i += 1
			if i==N-1: break
		if upnum>=K-1:
			count += 1
		i += 1

	ans = ans-max(count-1,0)

print(ans)