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


def slide_min(L: int, li: list):
	deq = deque()
	ret = []
	for i, x in enumerate(li):
		while deq and deq[-1][1] > x:
			deq.pop()
		deq.append((i, x))
		if deq[0][0] + L == i:
			deq.popleft()
		ret.append(deq[0][1])
	return ret[L - 1:]


def slide_max(L: int, li: list):
	deq = deque()
	ret = []
	for i, x in enumerate(li):
		while deq and deq[-1][1] < x:
			deq.pop()
		deq.append((i, x))
		if deq[0][0] + L == i:
			deq.popleft()
		ret.append(deq[0][1])
	return ret[L - 1:]


n, k, *a = map(int, open(0).read().split())
m, M = slide_min(k - 1, a), slide_max(k - 1, a)
ans = 1
for i in range(n - k):
	if not (a[i] < m[i + 1] and M[i + 1] < a[i + k]):
		ans += 1
cnt = 1
subt = 0
for x, y in zip(a, a[1:]):
	if x < y:
		cnt += 1
	else:
		cnt = 1
	if cnt == k:
		subt += 1
if subt:
	ans -= subt - 1

print(ans)