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, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees#, log2
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from fractions import gcd
from heapq import heappush, heappop, heapify
from functools import reduce, lru_cache
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7
#from decimal import *

N, K = MAP()
P = LIST()

check = [0]*(N-K+1)
up_check = [0]*N
for i in range(1, N):
	if P[i] >= P[i-1]:
		up_check[i] = 1

up_check_acc = list(accumulate(up_check))
for i in range(N-K+1):
	if up_check_acc[i+K-1]-up_check_acc[i] == K-1:
		check[i] = 1

q1 = sorted((P[:K]))
q2 = [N]
q3 = sorted([-x for x in P[:K]])
q4 = [N]

ans = N-K+1
for i, p in enumerate(P[K:]):
	heappush(q1, p)
	heappush(q3, -p)
	while q1[0] == q2[0]:
		heappop(q1)
		heappop(q2)

	while q3[0] == q4[0]:
		heappop(q3)
		heappop(q4)

	if q1[0] == P[i] and q3[0] == -p and check[i]*check[i+1] == 0:
		ans -= 1

	heappush(q2, P[i])
	heappush(q4, -P[i])

ans -= max(0, sum(check)-1)
print(ans)