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, defaultdict
import copy
import bisect
sys.setrecursionlimit(10 ** 9)
import math
import heapq
from itertools import product, permutations,combinations
import fractions

import sys
def input():
	return sys.stdin.readline().strip()

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

next_small = [N]*N
G = []
heapq.heapify(G)
heapq.heappush(G, (-P[0], 0))
for i in range(1, N):
	judge = 0
	while judge == 0 and len(G) > 0:
		num = heapq.heappop(G)
		if -num[0] < P[i]:
			heapq.heappush(G, num)
			judge = 1
		else:
			next_small[num[1]] = i
	heapq.heappush(G, (-P[i], i))

before_large = [-1]*N
G = []
heapq.heapify(G)
heapq.heappush(G, (P[N - 1], N - 1))
for i in range(N - 2, -1, -1):
	judge = 0
	while judge == 0 and len(G) > 0:
		num = heapq.heappop(G)
		if num[0] > P[i]:
			heapq.heappush(G, num)
			judge = 1
		else:
			before_large[num[1]] = i
	heapq.heappush(G, (P[i], i))

inc = [1]*N
for i in range(1, N):
	if P[i] > P[i - 1]:
		inc[i] = inc[i - 1] + 1

num = 0
zero = 0
if inc[K - 1] >= K:
	zero += 1

for i in range(1, N - K + 1):
	#print(i + K - 1)
	if inc[i + K - 1] >= K:
		zero += 1
	elif next_small[i - 1] >= i - 1 + K and before_large[i + K - 1] <= i - 1:
		num += 1

#print(inc, next_small, before_large)
print(N - K + 1 - num - max(0, (zero - 1)))