AtCoder Grand Contest 038 - Sorting a Segment

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

Source: atcoder | Difficulty: UNKNOWN_DIFFICULTY


Solutions:
(n, k) = map(int, input().split())
P = list(map(int, input().split()))
A = []
B = []
VA = [0] * n
VB = [0] * n
import heapq
for i in range(k):
	heapq.heappush(A, P[i])
	heapq.heappush(B, -P[i])
ans = 1
for i in range(n - k):
	b = -heapq.heappop(B)
	while VB[b] == 1:
		b = -heapq.heappop(B)
	a = heapq.heappop(A)
	while VA[a] == 1:
		a = heapq.heappop(A)
	if not (P[k + i] > b and P[i] == a):
		ans += 1
	heapq.heappush(A, a)
	heapq.heappush(B, -b)
	heapq.heappush(A, P[k + i])
	heapq.heappush(B, -P[k + i])
	VA[P[i]] = 1
	VB[P[i]] = 1
AA = []
for i in range(n - 1):
	if P[i + 1] - P[i] >= 0:
		AA.append(1)
	else:
		AA.append(0)
s = sum(AA[:k - 1])
t = 0
r = 0
if s == k - 1:
	t += 1
	r = 1
for i in range(n - k):
	s += AA[k - 1 + i]
	s -= AA[i]
	if s == k - 1:
		t += 1
		r += 1
	else:
		ans += max(0, r - 1)
		r = 0
ans += max(0, r - 1)
print(ans - max(0, t - 1))


class SWAG:

	def __init__(self, unit, f, data):
		self.unit = unit
		self.f = f
		self.fold_r = [unit]
		self.fold_l = [unit]
		self.data_r = []
		self.data_l = []
		sep = len(data) // 2
		for t in data[sep:]:
			self.append(t)
		for t in data[sep - 1::-1]:
			self.appendleft(t)

	def append(self, x):
		self.fold_r.append(self.f(self.fold_r[-1], x))
		self.data_r.append(x)

	def appendleft(self, x):
		self.fold_l.append(self.f(self.fold_l[-1], x))
		self.data_l.append(x)

	def pop(self):
		if not self.data_r:
			self.__init__(self.unit, self.f, self.data_l[::-1])
		self.fold_r.pop()
		return self.data_r.pop()

	def popleft(self):
		if not self.data_l:
			self.__init__(self.unit, self.f, self.data_r)
		self.fold_l.pop()
		return self.data_l.pop()

	def fold_all(self):
		return self.f(self.fold_r[-1], self.fold_l[-1])
(n, k, *p) = map(int, open(0).read().split())
c = [0]
for (a, b) in zip(p, p[1:]):
	c += (c[-1] + (a < b),)
(*c, f) = [b - a == k - 1 for (a, b) in zip(c, c[k - 1:])]
x = not f
s_min = SWAG(10 ** 18, min, p[:k - 1])
s_max = SWAG(0, max, p[1:k])
for (i, (a, b, c)) in enumerate(zip(p, p[k:], c)):
	f |= c
	s_min.append(p[i + k - 1])
	s_max.append(b)
	if not c and (a != s_min.fold_all() or b != s_max.fold_all()):
		x += 1
	s_min.popleft()
	s_max.popleft()
print(x + f)


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):
	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(N - K + 1 - num - max(0, zero - 1))


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

class Min_seg:

	def __init__(self, n, init_val, ide_ele=10 ** 9):
		self.ide_ele = ide_ele
		self.n = n
		self.num = 2 ** (self.n - 1).bit_length()
		self.seg = [self.ide_ele] * 2 * self.num
		for i in range(n):
			self.seg[i + self.num - 1] = init_val[i]
		for i in range(self.num - 2, -1, -1):
			self.seg[i] = min(self.seg[2 * i + 1], self.seg[2 * i + 2])

	def update(self, k, x):
		k += self.num - 1
		self.seg[k] = x
		while k + 1:
			k = (k - 1) // 2
			self.seg[k] = min(self.seg[k * 2 + 1], self.seg[k * 2 + 2])

	def query(self, p, q):
		if q <= p:
			return self.ide_ele
		p += self.num - 1
		q += self.num - 2
		res = self.ide_ele
		while q - p > 1:
			if p & 1 == 0:
				res = min(res, self.seg[p])
			if q & 1 == 1:
				res = min(res, self.seg[q])
				q -= 1
			p = p // 2
			q = (q - 1) // 2
		if p == q:
			res = min(res, self.seg[p])
		else:
			res = min(min(res, self.seg[p]), self.seg[q])
		return res

class Max_seg:

	def __init__(self, n, init_val, ide_ele=0):
		self.ide_ele = ide_ele
		self.n = n
		self.num = 2 ** (self.n - 1).bit_length()
		self.seg = [self.ide_ele] * 2 * self.num
		for i in range(n):
			self.seg[i + self.num - 1] = init_val[i]
		for i in range(self.num - 2, -1, -1):
			self.seg[i] = max(self.seg[2 * i + 1], self.seg[2 * i + 2])

	def update(self, k, x):
		k += self.num - 1
		self.seg[k] = x
		while k + 1:
			k = (k - 1) // 2
			self.seg[k] = max(self.seg[k * 2 + 1], self.seg[k * 2 + 2])

	def query(self, p, q):
		if q <= p:
			return self.ide_ele
		p += self.num - 1
		q += self.num - 2
		res = self.ide_ele
		while q - p > 1:
			if p & 1 == 0:
				res = max(res, self.seg[p])
			if q & 1 == 1:
				res = max(res, self.seg[q])
				q -= 1
			p = p // 2
			q = (q - 1) // 2
		if p == q:
			res = max(res, self.seg[p])
		else:
			res = max(max(res, self.seg[p]), self.seg[q])
		return res
(n, k) = map(int, input().split())
p = list(map(int, input().split()))
seg1 = Min_seg(n, p)
seg2 = Max_seg(n, p)
ans = n - k + 1
for i in range(n - k):
	if p[i] == seg1.query(i, i + k) and p[i + k] == seg2.query(i + 1, i + k + 1):
		ans -= 1
d = [0 for _ in range(n - 1)]
for i in range(n - 1):
	if p[i] < p[i + 1]:
		d[i] = 1
seg3 = Min_seg(n - 1, d)
data = [seg3.query(i, i + k - 1) for i in range(n - k + 1)]
if k > 2 and sum(data) > 1:
	now = -1
	for i in range(n - k + 1):
		if data[i] == 1:
			if i == 0:
				now += 1
			elif data[i - 1] == 0:
				now += 1
	ans -= now
print(ans)


from collections import Counter, deque
(N, K) = map(int, input().split())
P = list(map(int, input().split()))
ans = N - K + 1
LIS = [-1] * N
LIS[-1] = 1
LIS_MIN_NOW = P[-1]
for i in reversed(range(N - 1)):
	p = P[i]
	if p < LIS_MIN_NOW:
		LIS_MIN_NOW = p
		LIS[i] = LIS[i + 1] + 1
	else:
		LIS_MIN_NOW = p
		LIS[i] = 1
LIS = LIS[:N - K + 1]
slide_min = deque([])
MIN = []
for k in range(N):
	while slide_min and P[slide_min[-1]] >= P[k]:
		slide_min.pop()
	slide_min.append(k)
	if k < K - 1:
		continue
	if slide_min[0] + K <= k:
		slide_min.popleft()
	MIN.append(P[slide_min[0]])
slide_max = deque([])
MAX = []
for k in range(N):
	while slide_max and P[slide_max[-1]] <= P[k]:
		slide_max.pop()
	slide_max.append(k)
	if k < K - 1:
		continue
	if slide_max[0] + K <= k:
		slide_max.popleft()
	MAX.append(P[slide_max[0]])
for i in range(N - K + 1):
	flg = False
	if LIS[i] >= K:
		flg = True
	if i + 1 < N - K + 1 and P[i] == MIN[i] and (P[i + K] == MAX[i + 1]):
		flg = True
	ans -= flg
if len([l for l in LIS if l >= K]):
	ans += 1
print(ans)


class SegmentTree:

	def __init__(self, N, f, e=None):
		self.N = 1 << (N - 1).bit_length()
		self.seg = [e] * (self.N * 2)
		self.e = e
		self.f = f

	def build(self, A):
		for (i, a) in enumerate(A):
			self.seg[i + self.N] = a
		for i in range(self.N - 1, 0, -1):
			self.seg[i] = self.f(self.seg[i << 1], self.seg[i << 1 | 1])

	def update(self, i, x):
		i += self.N
		self.seg[i] = x
		while i > 1:
			self.seg[i >> 1] = self.f(self.seg[i], self.seg[i ^ 1])
			i >>= 1

	def query(self, a, b):
		L = R = self.e
		a += self.N
		b += self.N
		while a < b:
			if a & 1:
				L = self.f(L, self.seg[a])
				a += 1
			if b & 1:
				b -= 1
				R = self.f(self.seg[b], R)
			a >>= 1
			b >>= 1
		return self.f(L, R)
from collections import Counter

def main():
	(N, K, *P) = map(int, open(0).read().split())
	Mseg = SegmentTree(N, max, 0)
	mseg = SegmentTree(N, min, float('inf'))
	Mseg.build(P)
	mseg.build(P)
	D = Counter(P[:K])
	ans = 1
	als = 1
	for i in range(1, K):
		als = als + 1 if P[i] > P[i - 1] else 1
	iss = als == K
	for i in range(N - K):
		als = als + 1 if P[i + K] > P[i + K - 1] else 1
		mp = mseg.query(i, i + K)
		Mp = Mseg.query(i + 1, i + K + 1)
		if not (mp == P[i] and Mp == P[i + K]) and (not (iss and als == K)):
			ans += 1
		iss |= als == K
	print(ans)
main()


import sys
sys.setrecursionlimit(10000)

class SegmentTree:

	def __init__(self, array, f, ti):
		self.f = f
		self.ti = ti
		self.n = n = 2 ** len(array).bit_length()
		self.dat = dat = [ti] * n + array + [ti] * (n - len(array))
		for i in range(n - 1, 0, -1):
			dat[i] = f(dat[i << 1], dat[i << 1 | 1])

	def update(self, p, v):
		(f, n, dat) = (self.f, self.n, self.dat)
		p += n
		dat[p] = v
		while p > 1:
			p >>= 1
			dat[p] = f(dat[p << 1], dat[p << 1 | 1])

	def query(self, l, r):
		(f, ti, n, dat) = (self.f, self.ti, self.n, self.dat)
		res = ti
		l += n
		r += n
		while l < r:
			if l & 1:
				res = f(res, dat[l])
				l += 1
			if r & 1:
				r -= 1
				res = f(dat[r], res)
			l >>= 1
			r >>= 1
		return res

class UnionFind:

	def __init__(self, size):
		self.dat = list(range(size))
		self.SIZE = [1] * size

	def find(self, x):
		dat = self.dat
		stack = [x]
		while True:
			y = stack[-1]
			if dat[y] != y:
				stack += [dat[y]]
			else:
				break
		for s in stack:
			dat[s] = y
		return y

	def unite(self, x, y):
		is_same = self.is_same
		find = self.find
		SIZE = self.SIZE
		dat = self.dat
		if not is_same(x, y):
			(X, Y) = (find(x), find(y))
			(SX, SY) = (SIZE[X], SIZE[Y])
			if SX > SY:
				m = dat[X] = Y
			else:
				m = dat[Y] = X
			SIZE[m] = SX + SY
			SIZE[X + Y - m] = 0

	def is_same(self, x, y):
		find = self.find
		return find(x) == find(y)

	def scan_uf(self):
		find = self.find
		length = len(self.dat)
		for i in range(length):
			find(i)

	def size(self, x):
		return self.SIZE[self.find(x)]
(N, K) = [int(_) for _ in input().split()]
P = [int(_) for _ in input().split()]
STmax = SegmentTree(array=P, f=max, ti=-float('inf'))
STmin = SegmentTree(array=P, f=min, ti=float('inf'))
UF = UnionFind(N - K + 1)
for i in range(N - K):
	if P[i] == STmin.query(i, i + K) and P[i + K] == STmax.query(i + 1, i + K + 1):
		UF.unite(i, i + 1)
inc = 0
incK = []
for i in range(N - 2, -1, -1):
	if P[i] <= P[i + 1]:
		inc += 1
		if inc >= K - 1:
			incK += [i]
	else:
		inc = 0
for i in incK:
	UF.unite(incK[0], i)
UF.scan_uf()
print(len(set(UF.dat)))


class SegmentTree:

	def __init__(self, param, default, func):
		if isinstance(param, list):
			n = len(param)
		else:
			n = param
		self.d = default
		self.leaf = 1 << (n - 1).bit_length()
		if isinstance(param, list):
			self.tree = [default] * (self.leaf - 1) + param + [default] * (self.leaf - n)
			for i in range(self.leaf - 2, -1, -1):
				self.tree[i] = func(self.tree[i * 2 + 1], self.tree[i * 2 + 2])
		else:
			self.tree = [default] * (self.leaf * 2 - 1)
		self.f = func

	def find(self, i):
		return self.tree[i + self.leaf - 1]

	def merge(self, a, b):
		return self.f(a, b)

	def get_top(self):
		return self.tree[0]

	def query(self, a, b):
		T = self.tree
		(l, r) = (a + self.leaf - 1, b + self.leaf - 1)
		res = self.d
		while l < r:
			if not l % 2:
				res = self.merge(res, T[l])
				l += 1
			if not r % 2:
				r -= 1
				res = self.merge(res, T[r])
			l >>= 1
			r >>= 1
		return res

def main():
	inf = 10 ** 7
	(n, k) = map(int, input().split())
	P = list(map(int, input().split()))
	segmax = SegmentTree(P, 0, max)
	segmin = SegmentTree(P, inf, min)
	ans = n - k + 1
	for i in range(n - k):
		if segmin.query(i, i + k) == P[i] and segmax.query(i, i + k) < P[i + k]:
			ans -= 1
	tmp = 1
	cnt = 0
	for i in range(n - 1):
		if P[i] > P[i + 1]:
			if tmp >= k:
				cnt += 1
			tmp = 1
		else:
			tmp += 1
	if tmp >= k:
		cnt += 1
	ans -= max(0, cnt - 1)
	print(ans)
main()


from collections import Counter, deque
(N, K) = map(int, input().split())
P = list(map(int, input().split()))
ans = N - K + 1
LIS = [-1] * N
LIS[-1] = 1
LIS_MIN_NOW = P[-1]
for i in reversed(range(N - 1)):
	p = P[i]
	if p < LIS_MIN_NOW:
		LIS_MIN_NOW = p
		LIS[i] = LIS[i + 1] + 1
	else:
		LIS_MIN_NOW = p
		LIS[i] = 1
LIS = LIS[:N - K + 1]

def slide_min(A, K):
	(deq, ret) = (deque([]), [])
	for k in range(len(A)):
		while deq and A[deq[-1]] >= A[k]:
			deq.pop()
		deq.append(k)
		if k < K - 1:
			continue
		if deq[0] + K <= k:
			deq.popleft()
		ret.append(A[deq[0]])
	return ret
MIN = slide_min(P, K)
MAX = list(map(lambda x: -x, slide_min(list(map(lambda x: -x, P)), K)))
for i in range(N - K + 1):
	flg = False
	if LIS[i] >= K:
		flg = True
	if i + 1 < N - K + 1 and P[i] == MIN[i] and (P[i + K] == MAX[i + 1]):
		flg = True
	ans -= flg
if len([l for l in LIS if l >= K]):
	ans += 1
print(ans)


(n, k) = map(int, input().split())
raw = list(map(int, input().split()))
num = 2 ** (n - 1).bit_length()
seg1 = [0] * 2 * num
seg2 = [n] * 2 * num

def build(raw):
	for i in range(n):
		seg1[i + num - 1] = raw[i]
		seg2[i + num - 1] = raw[i]
	for i in range(num - 2, -1, -1):
		seg1[i] = max(seg1[2 * i + 1], seg1[2 * i + 2])
		seg2[i] = min(seg2[2 * i + 1], seg2[2 * i + 2])
	return True
build(raw)
cnt = n - k + 1

def query(seg, ele, segf, p, q):
	if q <= p:
		return False
	p += num - 1
	q += num - 2
	res = ele
	while q - p > 1:
		if not p % 2:
			res = segf(res, seg[p])
		if q % 2:
			res = segf(res, seg[q])
			q -= 1
		p //= 2
		q = (q - 1) // 2
	if p == q:
		res = segf(res, seg[p])
	else:
		res = segf(res, seg[p], seg[q])
	return res

def check(i):
	return query(seg1, 0, max, i, i + k + 1) == raw[i + k] and query(seg2, n + 1, min, i, i + k + 1) == raw[i]
t = [0] * n
f = -1
c = -1
for i in range(n):
	if raw[i] > c:
		f += 1
	else:
		f = 0
	c = raw[i]
	t[i] = f
c2 = -1
for i in range(n - k):
	if t[i + k - 1] - t[i] == k - 1:
		c2 += 1
	elif check(i):
		cnt -= 1
if t[n - 1] - t[n - k] == k - 1:
	c2 += 1
if c2 >= 0:
	cnt -= c2
print(cnt)


import sys
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
from math import floor, ceil, sqrt, factorial, log
from heapq import heappop, heappush, heappushpop
from collections import Counter, defaultdict, deque
from itertools import accumulate, permutations, combinations, product, combinations_with_replacement
from bisect import bisect_left, bisect_right
from copy import deepcopy
inf = float('inf')
mod = 10 ** 9 + 7

def pprint(*A):
	for a in A:
		print(*a, sep='\n')

def INT_(n):
	return int(n) - 1

def MI():
	return map(int, input().split())

def MF():
	return map(float, input().split())

def MI_():
	return map(INT_, input().split())

def LI():
	return list(MI())

def LI_():
	return [int(x) - 1 for x in input().split()]

def LF():
	return list(MF())

def LIN(n: int):
	return [I() for _ in range(n)]

def LLIN(n: int):
	return [LI() for _ in range(n)]

def LLIN_(n: int):
	return [LI_() for _ in range(n)]

def LLI():
	return [list(map(int, l.split())) for l in input()]

def I():
	return int(input())

def F():
	return float(input())

def ST():
	return input().replace('\n', '')

def main():
	(N, K) = MI()
	P = LI()
	max_heap = []
	min_heap = []
	includes = set()
	for i in range(K):
		x = P[i]
		heappush(max_heap, -x)
		heappush(min_heap, x)
		includes.add(x)
	wrongs = deque()
	for i in range(N - 1):
		if P[i] > P[i + 1]:
			wrongs.append(i + 0.5)
	including = deque()
	for w in deepcopy(wrongs):
		if w < K - 1:
			including.append(wrongs.popleft())
		else:
			break
	zero_experiense = not including
	ans = 1
	for left in range(1, N - K + 1):
		right = left + K - 1
		last_mem = P[left - 1]
		if including and including[0] < left:
			including.popleft()
		if wrongs and wrongs[0] < right:
			including.append(wrongs.popleft())
		includes.remove(last_mem)
		includes.add(P[right])
		while -max_heap[0] not in includes:
			heappop(max_heap)
		while min_heap[0] not in includes:
			heappop(min_heap)
		if last_mem < min_heap[0] and -max_heap[0] < P[right]:
			pass
		elif not including:
			if zero_experiense:
				pass
			else:
				ans += 1
				zero_experiense = True
		else:
			ans += 1
		heappush(min_heap, P[right])
		heappush(max_heap, -P[right])
	print(ans)
main()


from collections import deque
from itertools import accumulate

def slide_min(A, K):
	res = []
	Q = deque()
	for (i, a) in enumerate(A):
		while Q and A[Q[-1]] > a:
			Q.pop()
		Q.append(i)
		if Q[0] == i - K:
			Q.popleft()
		res.append(Q[0])
	return res[K - 1:]
(N, K, *P) = map(int, open(0).read().split())
mi = slide_min(P, K)
ma = slide_min([-p for p in P], K)
B = [mi != i or ma != i + K for (i, (mi, ma)) in enumerate(zip(mi, ma[1:]))]
A = [0] + list(accumulate((x < y for (x, y) in zip(P, P[1:]))))
S = [y - x != K - 1 for (x, y) in zip(A, A[K - 1:])]
ans = 1 + sum((b for (b, s) in zip(B, S[1:]) if s))
if S[0] and (not all(S)):
	ans += 1
print(ans)


from heapq import heappush, heappop
(N, K) = map(int, input().split())
A = list(map(int, input().split()))
h_max = []
h_min = []
for i in range(K):
	heappush(h_min, A[i])
	heappush(h_max, -A[i])
check = [0] * (N + 1)
tmp = [0] * N
tmp[0] = 1
for i in range(N - K):
	a_min = heappop(h_min)
	a_max = -heappop(h_max)
	while check[a_min]:
		a_min = heappop(h_min)
	while check[a_max]:
		a_max = -heappop(h_max)
	if A[i] == a_min and A[i + K] > a_max:
		tmp[i + 1] -= 1
	check[A[i]] = 1
	heappush(h_min, a_min)
	heappush(h_max, -a_max)
	heappush(h_min, A[i + K])
	heappush(h_max, -A[i + K])
	tmp[i + 1] += 1
B = [0]
for i in range(1, N):
	if A[i] > A[i - 1]:
		B.append(1)
	else:
		B.append(0)
sum_B = sum(B[1:K])
flag = 0
for i in range(N - K + 1):
	if sum_B == K - 1:
		if tmp[i]:
			flag = 1
			tmp[i] = 0
	if i == N - K:
		break
	sum_B = sum_B - B[i + 1] + B[i + K]
print(sum(tmp) + flag)


from heapq import heappush, heappop
(N, K, *P) = map(int, open(0).read().split())
mhq = []
Mhq = []
for c in P[:K]:
	heappush(mhq, c)
	heappush(Mhq, -c)
ans = 1
log = set()
for (i, c) in enumerate(P[K:]):
	while mhq[0] in log:
		heappop(mhq)
	while -Mhq[0] in log:
		heappop(Mhq)
	d = P[i]
	m = mhq[0]
	M = -Mhq[0]
	log.add(d)
	heappush(mhq, c)
	heappush(Mhq, -c)
	if not (m == d and M < c):
		ans += 1
p = P[0]
m = 1
x = 0
for c in P[1:]:
	if p < c:
		m += 1
	else:
		if m >= K:
			x += 1
		m = 1
	p = c
if m >= K:
	x += 1
if x != 0:
	ans -= x - 1
print(ans)


from collections import deque

class SlideMin:

	def __init__(self, leng):
		self.que = deque([])
		self.leng = leng

	def top(self):
		return self.que[0]

	def getQue(self):
		return self.que

	def update(self, index, value=0):
		while self.que:
			if self.que[-1][1] >= value:
				self.que.pop()
			else:
				break
		self.que.append((index, value))
		if self.que[0][0] == index - self.leng:
			self.que.popleft()
(N, K) = map(int, input().split())
P = list(map(int, input().split()))
maxQ = SlideMin(K)
minQ = SlideMin(K)
for i in range(K):
	maxQ.update(i, -P[i])
	minQ.update(i, P[i])
ans = 1
hasSame = False
seq = 1
for i in range(1, K):
	if P[i - 1] < P[i]:
		seq += 1
	else:
		seq = 1
if seq >= K:
	hasSame = True
for left in range(N - K):
	right = left + K
	if P[right - 1] < P[right]:
		seq += 1
	else:
		seq = 1
	maxQ.update(right, -P[right])
	if left == minQ.top()[0] and right == maxQ.top()[0]:
		pass
	elif seq < K:
		ans += 1
	elif not hasSame:
		hasSame = True
		ans += 1
	minQ.update(right, P[right])
print(ans)


from heapq import heappush, heappop
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations
import sys
import bisect
import string

def I():
	return int(input())

def MI():
	return map(int, input().split())

def LI():
	return [int(i) for i in input().split()]

def LI_():
	return [int(i) - 1 for i in input().split()]

def StoI():
	return [ord(i) - 97 for i in input()]

def show(*inp, end='\n'):
	if show_flg:
		print(*inp, end=end)
YN = ['Yes', 'No']
mo = 10 ** 9 + 7
input = sys.stdin.readline
show_flg = False
(n, k) = MI()
a = LI()

def slidmin(a, k):
	n = len(a)
	b = [0 for i in range(n - k + 1)]
	q = deque()
	for i in range(k):
		while q and a[q[-1]] >= a[i]:
			q.pop()
		q.append(i)
	b[0] = a[q[0]]
	s = len(q)
	for i in range(k, n):
		while q and a[q[-1]] >= a[i]:
			q.pop()
			s -= 1
		q.append(i)
		s += 1
		if q[0] <= i - k:
			q.popleft()
			s -= 1
		b[i - k + 1] = a[q[0]]
	return b
m = slidmin(a, k)
M = [-i for i in slidmin([-i for i in a], k)]
ans = 1
p = -1
c = 0
for i in range(k):
	if p < a[i]:
		c += 1
	else:
		c = 1
	p = a[i]
fl = True if c == k else False
for i in range(n - k):
	if p < a[i + k]:
		c += 1
	else:
		c = 1
	p = a[i + k]
	inc = 1
	if c == k:
		if fl:
			inc = 0
		fl = True
	if a[i] == m[i] and a[i + k] == M[i + 1]:
		inc = 0
	ans += inc
print(ans)


def make_tree(n):
	i = 2
	while True:
		if i >= n * 2:
			tree1 = [inf] * i
			tree2 = [0] * i
			break
		else:
			i *= 2
	return (tree1, tree2)

def update(i, x):
	j = len(tree1) // 2 + i
	tree1[j] = x
	j //= 2
	while True:
		if j == 0:
			break
		tree1[j] = min(tree1[2 * j], tree1[2 * j + 1])
		j //= 2
	j = len(tree2) // 2 + i
	tree2[j] = x
	j //= 2
	while True:
		if j == 0:
			break
		tree2[j] = max(tree2[2 * j], tree2[2 * j + 1])
		j //= 2
	return

def find(x, y):
	s = len(tree1) // 2 + x
	t = len(tree1) // 2 + y
	ans1 = inf
	while True:
		if s > t:
			break
		if s % 2 == 0:
			s //= 2
		else:
			ans1 = min(ans1, tree1[s])
			s = (s + 1) // 2
		if t % 2 == 1:
			t //= 2
		else:
			ans1 = min(ans1, tree1[t])
			t = (t - 1) // 2
	s = len(tree2) // 2 + x
	t = len(tree2) // 2 + y
	ans2 = 0
	while True:
		if s > t:
			break
		if s % 2 == 0:
			s //= 2
		else:
			ans2 = max(ans2, tree2[s])
			s = (s + 1) // 2
		if t % 2 == 1:
			t //= 2
		else:
			ans2 = max(ans2, tree2[t])
			t = (t - 1) // 2
	return (ans1, ans2)
(n, k) = map(int, input().split())
p = list(map(int, input().split()))
ans = n - k + 1
s = [1] * n
for i in range(1, n):
	if p[i] > p[i - 1]:
		s[i] = s[i - 1] + 1
ans -= max(s.count(k) - 1, 0)
inf = pow(10, 7)
(tree1, tree2) = make_tree(n)
for i in range(n):
	update(i, p[i])
for i in range(n - k):
	(a, b) = find(i, i + k)
	if a == p[i] and b == p[i + k]:
		ans -= 1
print(ans)


import sys
sys.setrecursionlimit(10 ** 7)
import math
from copy import copy, deepcopy
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right
from collections import deque
from collections import Counter
from itertools import accumulate
from heapq import heapify, heappop, heappush
from functools import lru_cache

def input():
	return sys.stdin.readline()[:-1]

def printl(li):
	print(*li, sep='\n')

def argsort(s, return_sorted=False):
	inds = sorted(range(len(s)), key=lambda k: s[k])
	if return_sorted:
		return (inds, [s[i] for i in inds])
	return inds

def alp2num(c, cap=False):
	return ord(c) - 97 if not cap else ord(c) - 65

def num2alp(i, cap=False):
	return chr(i + 97) if not cap else chr(i + 65)

def matmat(A, B):
	(K, N, M) = (len(B), len(A), len(B[0]))
	return [[sum([A[i][k] * B[k][j] for k in range(K)]) for j in range(M)] for i in range(N)]

def matvec(M, v):
	(N, size) = (len(v), len(M))
	return [sum([M[i][j] * v[j] for j in range(N)]) for i in range(size)]

def T(M):
	(n, m) = (len(M), len(M[0]))
	return [[M[j][i] for j in range(n)] for i in range(m)]

class BIT:

	def __init__(self, max_n):
		self.size = max_n + 1
		self.tree = [0] * self.size
		self.depth = self.size.bit_length()

	def initialize(self, seq):
		tree = self.tree
		size = self.size
		for (i, x) in enumerate(seq, 1):
			tree[i] += x
			j = i + (i & -i)
			if j < size:
				tree[j] += tree[i]

	def __repr__(self):
		return self.tree.__repr__()

	def get_sum(self, i):
		tree = self.tree
		s = 0
		while i:
			s += tree[i]
			i -= i & -i
		return s

	def add(self, i, x):
		tree = self.tree
		size = self.size
		while i < size:
			tree[i] += x
			i += i & -i

	def find_kth_element(self, k):
		tree = self.tree
		size = self.size
		(x, sx) = (0, 0)
		dx = 1 << self.depth
		for i in range(self.depth - 1, -1, -1):
			dx = 1 << i
			if x + dx >= size:
				continue
			y = x + dx
			sy = sx + tree[y]
			if sy < k:
				(x, sx) = (y, sy)
		return x + 1

def main():
	mod = 10 ** 9 + 7
	(N, K) = map(int, input().split())
	Ps = tuple(map(int, input().split()))
	bit = BIT(N + 1)
	sc = 1
	tot = 0
	j = 0
	cur = Ps[0]
	flag = 1
	cur = Ps[0]
	it = 0
	for (i, p) in enumerate(Ps[:K]):
		if cur > p:
			it = i
		bit.add(p + 1, 1)
		cur = p
	count = 0
	if it == 0:
		count = 1
	for i in range(N - K + 1):
		j = i + K - 1
		tot += sc
		if i == N - K:
			break
		a = Ps[i]
		b = Ps[i + K]
		if bit.find_kth_element(1) == a + 1 and bit.find_kth_element(K) <= b + 1:
			sc = 0
		else:
			sc = 1
		bit.add(a + 1, -1)
		bit.add(b + 1, 1)
		j = i + K
		if Ps[j - 1] > Ps[j]:
			it = j
		elif j - it + 1 >= K:
			if count > 0:
				sc = 0
			else:
				count = 1
		cur = Ps[j]
	print(tot)
main()


class SegmentTree:

	def __init__(self, n, op, e):
		self.n = n
		self.op = op
		self.e = e
		self.size = 1 << (self.n - 1).bit_length()
		self.tree = [self.e] * (self.size << 1)

	def built(self, array):
		for i in range(self.n):
			self.tree[self.size + i] = array[i]
		for i in range(self.size - 1, 0, -1):
			self.tree[i] = self.op(self.tree[i << 1], self.tree[i << 1 | 1])

	def update(self, i, x):
		i += self.size
		self.tree[i] = x
		while i > 1:
			i >>= 1
			self.tree[i] = self.op(self.tree[i << 1], self.tree[i << 1 | 1])

	def get(self, l, r):
		l += self.size
		r += self.size
		res_l = self.e
		res_r = self.e
		while l < r:
			if l & 1:
				res_l = self.op(res_l, self.tree[l])
				l += 1
			if r & 1:
				r -= 1
				res_r = self.op(self.tree[r], res_r)
			l >>= 1
			r >>= 1
		return self.op(res_l, res_r)

	def __iter__(self):
		for a in self.tree[self.size:self.size + self.n]:
			yield a

	def __str__(self):
		return str(self.tree[self.size:self.size + self.n])
import sys
input = sys.stdin.readline
(N, K) = map(int, input().split())
P = list(map(int, input().split()))
e = float('inf')
op = lambda x, y: x if x < y else y
st1 = SegmentTree(N, op, e)
st1.built(P)
e = 0
op = lambda x, y: x if x > y else y
st2 = SegmentTree(N, op, e)
st2.built(P)
Q = [1]
for i in range(N - 1):
	if P[i] < P[i + 1]:
		Q.append(Q[-1] + 1)
	else:
		Q.append(1)
(res, flg) = (1, 0)
if Q[K - 1] >= K:
	flg = 1
for i in range(1, N - K + 1):
	(mi, ma) = (st1.get(i, i + K - 1), st2.get(i, i + K - 1))
	if P[i + K - 1] < ma or P[i - 1] > mi:
		if Q[i + K - 1] < K:
			res += 1
		elif not flg:
			res += 1
			flg = 1
print(res)


import sys
from collections import deque
from itertools import accumulate
sr = lambda : sys.stdin.readline().rstrip()
ir = lambda : int(sr())
lr = lambda : list(map(int, sr().split()))

def slide_min(A, K):
	res = []
	Q = deque()
	for (i, a) in enumerate(A):
		while Q and A[Q[-1]] > a:
			Q.pop()
		Q.append(i)
		if Q[0] == i - K:
			Q.popleft()
		res.append(Q[0])
	return res[K - 1:]
(N, K) = lr()
P = lr()
mi = slide_min(P, K)
ma = slide_min([-x for x in P], K)
new_pattern = [not (mi == i and ma == i + K) for (i, (mi, ma)) in enumerate(zip(mi, ma[1:]))]
increase = [0] + list(accumulate((x < y for (x, y) in zip(P, P[1:]))))
stable_increase = [y - x == K - 1 for (x, y) in zip(increase, increase[K - 1:])]
answer = 1 + sum([x for (x, y) in zip(new_pattern, stable_increase[1:]) if not y])
if not stable_increase[0] and any(stable_increase):
	answer += 1
print(answer)


(N, K) = map(int, input().split())
N += 1
N0 = 2 ** (N - 1).bit_length()
INF = float('inf')
minST = [INF] * (2 * N0)

def update_min(k, x):
	k += N0 - 1
	minST[k] = x
	while k >= 0:
		k = (k - 1) // 2
		minST[k] = min(minST[2 * k + 1], minST[2 * k + 2])

def query_min(l, r):
	L = l + N0
	R = r + N0
	s = INF
	while L < R:
		if R & 1:
			R -= 1
			s = min(s, minST[R - 1])
		if L & 1:
			s = min(s, minST[L - 1])
			L += 1
		L >>= 1
		R >>= 1
	return s
MINF = float('-inf')
maxST = [MINF] * (2 * N0)

def update_max(k, x):
	k += N0 - 1
	maxST[k] = x
	while k >= 0:
		k = (k - 1) // 2
		maxST[k] = max(maxST[2 * k + 1], maxST[2 * k + 2])

def query_max(l, r):
	L = l + N0
	R = r + N0
	s = MINF
	while L < R:
		if R & 1:
			R -= 1
			s = max(s, maxST[R - 1])
		if L & 1:
			s = max(s, maxST[L - 1])
			L += 1
		L >>= 1
		R >>= 1
	return s
Ps = list(map(int, input().split())) + [-1]
sorted_lens = []
tmp = 0
prev = -1
for (i, p) in enumerate(Ps):
	update_min(i, p)
	update_max(i, p)
	if prev > p:
		tmp = 0
	tmp += 1
	sorted_lens.append(tmp)
	prev = p
ans = N - K
flag = False
for i in range(N - K):
	smin = query_min(i, i + K + 1)
	smax = query_max(i, i + K + 1)
	if smin == Ps[i] and smax == Ps[i + K] or (flag and sorted_lens[i + K] >= K):
		ans -= 1
	if sorted_lens[i + K - 1] == K:
		flag = True
print(ans)


class SegmentTree(object):

	def __init__(self, init_array, seg_func=min, seg_func_null=10 ** 9 + 7):
		self.seg_func = seg_func
		self.seg_func_null = seg_func_null
		self.n = 1
		while self.n < len(init_array):
			self.n *= 2
		self.dat = [0] * (2 * self.n - 1)
		for i in range(len(init_array)):
			self.dat[self.n - 1 + i] = init_array[i]
		for i in range(self.n - 2, -1, -1):
			self.dat[i] = self.seg_func(self.dat[2 * i + 1], self.dat[2 * i + 2])

	def update(self, k, a):
		k += self.n - 1
		self.dat[k] = a
		while k > 0:
			k = (k - 1) // 2
			self.dat[k] = self.seg_func(self.dat[k * 2 + 1], self.dat[k * 2 + 2])

	def query(self, p, q):
		if q <= p:
			return self.seg_func_null
		p += self.n - 1
		q += self.n - 2
		res = self.seg_func_null
		while q - p > 1:
			if p & 1 == 0:
				res = self.seg_func(res, self.dat[p])
			if q & 1 == 1:
				res = self.seg_func(res, self.dat[q])
				q -= 1
			p = p // 2
			q = (q - 1) // 2
		if p == q:
			res = self.seg_func(res, self.dat[p])
		else:
			res = self.seg_func(self.seg_func(res, self.dat[p]), self.dat[q])
		return res

def solve_b(n, k, p_list):
	min_tree = SegmentTree(p_list)
	max_tree = SegmentTree(p_list, max, -1)
	min_list = [0] * n
	max_list = [0] * n
	for i in range(n - k + 1):
		if p_list[i] == min_tree.query(i, i + k):
			min_list[i] = 1
	for i in range(n - k + 1):
		if p_list[i + k - 1] == max_tree.query(i, i + k):
			max_list[i + k - 1] = 1
	res = 1
	for i in range(n - k):
		if min_list[i] == 0 or max_list[i + k] == 0:
			res += 1
	straight = 1
	count_k = 0
	for i in range(n - 1):
		if p_list[i] < p_list[i + 1]:
			straight += 1
		else:
			straight = 1
		if straight == k:
			count_k += 1
	if count_k > 0:
		res -= count_k - 1
	return res

def solve_b_greedy(n, k, p_list):
	count_dict = dict()
	for i in range(n - k + 1):
		p_list_new = p_list[:i] + list(sorted(p_list[i:i + k])) + p_list[i + k:]
		p_list_new_hash = '.'.join([str(p) for p in p_list_new])
		if p_list_new_hash in count_dict.keys():
			print(i, p_list_new_hash)
		count_dict[p_list_new_hash] = 1
	return len(count_dict)

def main_greed():
	(n, k) = map(int, input().split())
	p_list = list(map(int, input().split()))
	res = solve_b_greedy(n, k, p_list)
	print(res)

def main():
	(n, k) = map(int, input().split())
	p_list = list(map(int, input().split()))
	res = solve_b(n, k, p_list)
	print(res)
main()


from collections import deque
(n, k) = map(int, input().split())
a = list(map(int, input().split()))
k -= 1
mnlist = []
q = deque([0])
for i in range(1, k):
	while q:
		x = q.pop()
		if a[i] > a[x]:
			q.append(x)
			q.append(i)
			break
	if not q:
		q.append(i)
for i in range(k, n + 1):
	t = q.popleft()
	mnlist.append(a[t])
	if t != i - k:
		q.appendleft(t)
	if i == n:
		break
	while q:
		x = q.pop()
		if a[i] > a[x]:
			q.append(x)
			q.append(i)
			break
	if not q:
		q.append(i)
mxlist = []
q = deque([0])
for i in range(1, k):
	while q:
		x = q.pop()
		if a[i] < a[x]:
			q.append(x)
			q.append(i)
			break
	if not q:
		q.append(i)
for i in range(k, n + 1):
	t = q.popleft()
	mxlist.append(a[t])
	if t != i - k:
		q.appendleft(t)
	if i == n:
		break
	while q:
		x = q.pop()
		if a[i] < a[x]:
			q.append(x)
			q.append(i)
			break
	if not q:
		q.append(i)
ans = n - k
r = set()
for i in range(1, n - k):
	if a[i - 1] < mnlist[i] and mxlist[i] < a[i + k]:
		r.add(i)
flg = 0
flg2 = 0
for i in range(1, n):
	if a[i - 1] < a[i]:
		flg += 1
	else:
		flg = 0
	if flg >= k:
		r.add(i - k)
		flg2 = 1
print(ans - len(r) + flg2)


import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop, heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10 ** 9 + 7
inf = float('inf')

def I():
	return int(sys.stdin.readline())

def LI():
	return list(map(int, sys.stdin.readline().split()))
(n, k) = LI()
p = LI()
ans = 0
que = deque()
que.append(0)
minlst = []
for i in range(1, n):
	if p[que[-1]] < p[i]:
		que.append(i)
	else:
		while que:
			if p[que[-1]] < p[i]:
				que.append(i)
				break
			else:
				que.pop()
		else:
			que.append(i)
	if i >= k:
		minlst.append(p[que[0]])
		if que[0] == i - k:
			que.popleft()
minlst.append(p[que[0]])
que = deque()
que.append(0)
maxlst = []
for i in range(1, n):
	if p[que[-1]] > p[i]:
		que.append(i)
	else:
		while que:
			if p[que[-1]] > p[i]:
				que.append(i)
				break
			else:
				que.pop()
		else:
			que.append(i)
	if i >= k - 1:
		maxlst.append(p[que[0]])
		if que[0] == i - k:
			que.popleft()

def root(x):
	if par[x] == x:
		return x
	par[x] = root(par[x])
	return par[x]

def union(x, y):
	x = root(x)
	y = root(y)
	if rank[x] < rank[y]:
		par[x] = y
	else:
		par[y] = x
		if rank[x] == rank[y]:
			rank[x] += 1
lst = []
cnt = 1
tmp = p[0]
for i in range(1, n):
	if tmp < p[i]:
		cnt += 1
	else:
		if cnt >= k:
			lst.append(i - k)
		cnt = 1
	tmp = p[i]
if cnt >= k:
	lst.append(i - cnt + 1)
par = [i for i in range(n)]
rank = [0] * n
if len(lst) > 1:
	for i in lst:
		for j in lst[::-1]:
			union(i, j)
for i in range(n - k):
	if p[i] == minlst[i] and p[i + k] == maxlst[i + 1]:
		union(i, i + 1)
s = set()
for i in range(n - k + 1):
	s.add(root(i))
print(len(s))


class SegmentTree:

	@classmethod
	def all_identity(cls, operator, identity, size):
		return cls(operator, identity, [identity] * (2 << (size - 1).bit_length()))

	@classmethod
	def from_initial_data(cls, operator, identity, data):
		size = 1 << (len(data) - 1).bit_length()
		temp = [identity] * (2 * size)
		temp[size:size + len(data)] = data
		data = temp
		for i in reversed(range(size)):
			data[i] = operator(data[2 * i], data[2 * i + 1])
		return cls(operator, identity, data)

	def __init__(self, operator, identity, data):
		self.op = operator
		self.id = identity
		self.data = data
		self.size = len(data) // 2

	def _interval(self, a, b):
		a += self.size
		b += self.size
		ra = self.id
		rb = self.id
		data = self.data
		op = self.op
		while a < b:
			if a & 1:
				ra = op(ra, data[a])
				a += 1
			if b & 1:
				b -= 1
				rb = op(data[b], rb)
			a >>= 1
			b >>= 1
		return op(ra, rb)

	def __getitem__(self, i):
		if isinstance(i, slice):
			return self._interval(0 if i.start is None else i.start, self.size if i.stop is None else i.stop)
		elif isinstance(i, int):
			return self.data[i + self.size]

	def __setitem__(self, i, v):
		i += self.size
		data = self.data
		op = self.op
		while i:
			data[i] = v
			v = op(data[i ^ 1], v) if i & 1 else op(v, data[i ^ 1])
			i >>= 1

	def __iter__(self):
		return iter(self.data[self.size:])
max2 = lambda x, y: x if x > y else y
min2 = lambda x, y: x if x < y else y

def solve(K, P):
	N = len(P)
	maxseg = SegmentTree.from_initial_data(max2, -1, P)
	minseg = SegmentTree.from_initial_data(min2, N, P)
	delta = [b - a for (a, b) in zip(P, P[1:])]
	deltaseg = SegmentTree.from_initial_data(min2, N, delta)
	c = 1
	sorted_ever_counted = deltaseg[:K - 1] > 0
	for i in range(N - K):
		a = maxseg[i + 1:i + K]
		b = minseg[i + 1:i + K]
		is_sorted = deltaseg[i + 1:i + K] > 0
		if b < P[i] or a > P[i + K]:
			if is_sorted:
				c += int(not sorted_ever_counted)
				sorted_ever_counted = True
			else:
				c += 1
	return c
(N, K) = map(int, input().split())
P = list(map(int, input().split()))
print(solve(K, P))


from heapq import heapify, heappush, heappop

def solve():
	(N, K) = map(int, input().split())
	Ps = list(map(int, input().split()))
	ans = N - K + 1
	numAsc = 0
	num = 0
	P0 = -1
	for P in Ps + [-1]:
		if P0 < P:
			num += 1
		else:
			if num >= K:
				numAsc += num - K + 1
			num = 1
		P0 = P
	if numAsc > 0:
		ans -= numAsc - 1
	if K > 2:
		mins = [N] * N
		P = min(Ps[:K + 1])
		mins[0] = P
		PQ = [(P, i) for (i, P) in enumerate(Ps[:K + 1])]
		heapify(PQ)
		for i in range(K + 1, N):
			heappush(PQ, (Ps[i], i))
			while True:
				(P, pos) = heappop(PQ)
				if i - K <= pos:
					mins[i - K] = P
					heappush(PQ, (P, pos))
					break
		maxs = [-1] * N
		P = max(Ps[:K + 1])
		maxs[0] = P
		PQ = [(-P, i) for (i, P) in enumerate(Ps[:K + 1])]
		heapify(PQ)
		for i in range(K + 1, N):
			heappush(PQ, (-Ps[i], i))
			while True:
				(P, pos) = heappop(PQ)
				if i - K <= pos:
					maxs[i - K] = -P
					heappush(PQ, (P, pos))
					break
		isSorteds = [False] * N
		num = 0
		P0 = -1
		for (i, P) in enumerate(Ps + [-1]):
			if P0 < P:
				num += 1
				if num >= K - 1:
					isSorteds[i - K + 1] = True
			else:
				if num >= K:
					numAsc += num - K + 1
				num = 1
			P0 = P
		for i in range(N - K):
			(L, R) = (Ps[i], Ps[i + K])
			(minK, maxK) = (mins[i], maxs[i])
			if L == minK and R == maxK and (not isSorteds[i]):
				ans -= 1
	print(ans)
solve()


import heapq

def main():
	(N, K) = map(int, input().split())
	P = list(map(int, input().split()))
	ans = 1
	inside_que = [0] * N
	(min_que, max_que) = ([], [])
	for i in range(K):
		heapq.heappush(min_que, P[i])
		heapq.heappush(max_que, -P[i])
		inside_que[P[i]] = 1
	for i in range(N - K):
		(old_p, new_p) = (P[i], P[i + K])
		if not (old_p == min_que[0] and new_p >= -max_que[0]):
			ans += 1
		inside_que[old_p] = 0
		inside_que[new_p] = 1
		heapq.heappush(min_que, new_p)
		heapq.heappush(max_que, -new_p)
		while inside_que[min_que[0]] == 0:
			heapq.heappop(min_que)
		while inside_que[-max_que[0]] == 0:
			heapq.heappop(max_que)
	desc_index = 0
	exists_asc_section = False
	for i in range(1, N):
		if P[i - 1] > P[i]:
			if i - desc_index >= K:
				ans -= 1
				exists_asc_section = True
			desc_index = i
	if N - desc_index >= K:
		exists_asc_section = True
		ans -= 1
	if exists_asc_section:
		ans += 1
	print(ans)
main()


import sys
input = sys.stdin.readline
(N, K) = map(int, input().split())
P = list(map(int, input().split()))
count = 0
first = 1

def init(init_val, n):
	for i in range(n):
		seg[i + num - 1] = init_val[i]
	for i in range(num - 2, -1, -1):
		seg[i] = segfunc(seg[2 * i + 1], seg[2 * i + 2])

def segfunc(x, y):
	return max([x, y])

def update(k, x):
	k += num - 1
	seg[k] = x
	while k:
		k = (k - 1) // 2
		seg[k] = segfunc(seg[k * 2 + 1], seg[k * 2 + 2])

def query(p, q):
	if q <= p:
		return ide_ele
	p += num - 1
	q += num - 2
	res = ide_ele
	while q - p > 1:
		if p & 1 == 0:
			res = segfunc(res, seg[p])
		if q & 1 == 1:
			res = segfunc(res, seg[q])
			q -= 1
		p = p // 2
		q = (q - 1) // 2
	if p == q:
		res = segfunc(res, seg[p])
	else:
		res = segfunc(segfunc(res, seg[p]), seg[q])
	return res
ide_ele = 0
num = 2 ** (N - 1).bit_length()
seg = [ide_ele] * 2 * num

def init2(init_val, n):
	for i in range(n):
		seg2[i + num - 1] = init_val[i]
	for i in range(num - 2, -1, -1):
		seg2[i] = segfunc2(seg2[2 * i + 1], seg2[2 * i + 2])

def segfunc2(x, y):
	return min([x, y])

def update2(k, x):
	k += num - 1
	seg2[k] = x
	while k:
		k = (k - 1) // 2
		seg2[k] = segfunc2(seg2[k * 2 + 1], seg2[k * 2 + 2])

def query2(p, q):
	if q <= p:
		return ide_ele2
	p += num - 1
	q += num - 2
	res = ide_ele2
	while q - p > 1:
		if p & 1 == 0:
			res = segfunc2(res, seg2[p])
		if q & 1 == 1:
			res = segfunc2(res, seg2[q])
			q -= 1
		p = p // 2
		q = (q - 1) // 2
	if p == q:
		res = segfunc2(res, seg2[p])
	else:
		res = segfunc2(segfunc2(res, seg2[p]), seg2[q])
	return res
ide_ele2 = 10 ** 9
num = 2 ** (N - 1).bit_length()
seg2 = [ide_ele2] * 2 * num
l = [0] * (N - 1)
for i in range(len(l)):
	if P[i] >= P[i + 1]:
		l[i] = 1
l2 = [0] * (N - K + 1)
tmp = sum(l[0:K - 1])
for i in range(N - K + 1):
	if tmp == 0:
		l2[i] = 1
	if i != N - K:
		tmp += l[i + K - 1] - l[i]
init(P, N)
init2(P, N)
for i in range(N - K + 1):
	if l2[i] == 1:
		if first == 1:
			count += 1
			first = 0
		continue
	elif P[i - 1] < query2(i, i + K - 1) and P[i + K - 1] > query(i, i + K - 1) and (i != 0):
		continue
	else:
		count += 1
print(count)


import sys
from heapq import *
input = sys.stdin.readline

def solve(n, k, p):
	res = n - k + 1
	count = 0
	length = 1
	judge_max = [-x for x in p[:k]]
	judge_min = p[:k]
	heapify(judge_max)
	heapify(judge_min)
	already = [False] * n
	for i in range(k - 1):
		if p[i] < p[i + 1]:
			length += 1
		else:
			length = 1
	if length == k:
		count += 1
	for i in range(k - 1, n - 1):
		if p[i] < p[i + 1]:
			length += 1
		else:
			length = 1
		already[p[i - k + 1]] = True
		while True:
			vmax = -judge_max[0]
			if already[vmax]:
				heappop(judge_max)
				continue
			else:
				break
		while True:
			vmin = judge_min[0]
			if already[vmin]:
				heappop(judge_min)
				continue
			else:
				break
		if p[i - k + 1] < vmin and vmax < p[i + 1]:
			res -= 1
		elif length >= k:
			if count:
				res -= 1
			count += 1
		heappush(judge_max, -p[i + 1])
		heappush(judge_min, p[i + 1])
	return res

def main():
	(n, k) = map(int, input().split())
	p = list(map(int, input().split()))
	ans = solve(n, k, p)
	print(ans)
main()


from operator import add

class SegTree:

	def __init__(self, N, e, operator_func=add):
		self.e = e
		self.size = N
		self.node = [self.e] * (2 * N)
		self.operator_func = operator_func

	def set_list(self, l):
		for i in range(self.size):
			self.node[i + self.size - 1] = l[i]
		for i in range(self.size - 1)[::-1]:
			self.node[i] = self.operator_func(self.node[2 * i + 1], self.node[2 * i + 2])

	def update(self, k, x):
		k += self.size - 1
		self.node[k] = x
		while k >= 0:
			k = (k - 1) // 2
			self.node[k] = self.operator_func(self.node[2 * k + 1], self.node[2 * k + 2])

	def get(self, l, r):
		x = self.e
		l += self.size
		r += self.size
		while l < r:
			if l & 1:
				x = self.operator_func(x, self.node[l - 1])
				l += 1
			if r & 1:
				r -= 1
				x = self.operator_func(x, self.node[r - 1])
			l >>= 1
			r >>= 1
		return x
(N, K) = map(int, input().split())
(*P,) = map(int, input().split())
INF = 10 ** 12
tree_max = SegTree(N, -INF, operator_func=max)
tree_max.set_list(P)
tree_min = SegTree(N, INF, operator_func=min)
tree_min.set_list(P)
tree_monoinc = SegTree(N, INF, operator_func=min)
for i in range(N):
	tree_monoinc.update(i, P[i] - P[i - 1] if i else 0)

def isMonoinc(l, r):
	l += 1
	return tree_monoinc.get(l, r) >= 0
ans = N - K + 1
orig = 0
for i in range(N - K + 1):
	if isMonoinc(i, i + K):
		orig = 1
		ans -= 1
	elif i + K < N and tree_max.get(i, i + K + 1) == P[i + K] and (tree_min.get(i, i + K + 1) == P[i]):
		ans -= 1
ans += orig
print(ans)


from collections import defaultdict, deque
import sys
buff_readline = sys.stdin.readline
readline = sys.stdin.readline
INF = 2 ** 62 - 1

def read_int():
	return int(buff_readline())

def read_int_n():
	return list(map(int, buff_readline().split()))

def read_float():
	return float(buff_readline())

def read_float_n():
	return list(map(float, buff_readline().split()))

def read_str():
	return readline().strip()

def read_str_n():
	return readline().strip().split()

def error_print(*args):
	print(*args, file=sys.stderr)

def mt(f):
	import time

	def wrap(*args, **kwargs):
		s = time.time()
		ret = f(*args, **kwargs)
		e = time.time()
		error_print(e - s, 'sec')
		return ret
	return wrap

class SegmentTree:

	def __init__(self, array, operator, identity_element):
		_len = len(array)
		self.__op = operator
		self.__size = 1 << (_len - 1).bit_length()
		self.__tree = [identity_element] * self.__size + array + [identity_element] * (self.__size - _len)
		self.__ie = identity_element
		for i in range(self.__size - 1, 0, -1):
			self.__tree[i] = operator(self.__tree[i * 2], self.__tree[i * 2 + 1])

	def update(self, i, v):
		i += self.__size
		self.__tree[i] = v
		while i:
			i //= 2
			self.__tree[i] = self.__op(self.__tree[i * 2], self.__tree[i * 2 + 1])

	def query(self, l, r):
		l += self.__size
		r += self.__size
		ret = self.__ie
		while l < r:
			if l & 1:
				ret = self.__op(ret, self.__tree[l])
				l += 1
			if r & 1:
				r -= 1
				ret = self.__op(ret, self.__tree[r])
			l //= 2
			r //= 2
		return ret

@mt
def slv(N, K, P):
	min_st = SegmentTree(P, min, INF)
	max_st = SegmentTree(P, max, -1)
	a = []
	for i in range(N - K):
		min_p = min_st.query(i, i + K + 1)
		max_p = max_st.query(i, i + K + 1)
		if P[i] == min_p and P[i + K] == max_p:
			a.append((i, i + K))
	j = 0
	ss = []
	for i in range(N - 1):
		if P[i] < P[i + 1]:
			pass
		else:
			if i - j + 1 >= K:
				ss.append((j, i + 1))
			j = i + 1
	i += 1
	if i - j + 1 >= K:
		ss.append((j, i + 1))
	ans = N - K + 1
	if ss:
		ans -= sum((s[1] - s[0] - K + 1 for s in ss)) - 1
	ss.reverse()
	for (l, r) in a:
		while ss and ss[-1][1] <= l:
			ss.pop()
		if ss:
			if ss[-1][0] <= l and r < ss[-1][1]:
				pass
			else:
				ans -= 1
		else:
			ans -= 1
	return ans

def ref(N, K, P):
	ans = set()
	for i in range(N - K + 1):
		s = tuple(P[:i] + sorted(P[i:i + K]) + P[i + K:])
		ans.add(s)
	return len(ans)

def main():
	(N, K) = read_int_n()
	P = read_int_n()
	print(slv(N, K, P))
main()


from collections import deque
(N, K) = map(int, input().split())
P = list(map(int, input().split()))
smin = deque()
smax = deque()
x = 0
r = 0
r2 = 0
for (i, p) in enumerate(P):
	while len(smin) > 0 and P[smin[-1]] > p:
		smin.pop()
	smin.append(i)
	if smin[0] <= i - K:
		smin.popleft()
	while len(smax) > 0 and P[smax[-1]] < p:
		smax.pop()
	smax.append(i)
	if smax[0] <= i - K:
		smax.popleft()
	if i > 0 and P[i - 1] < P[i]:
		x = min(x + 1, K - 1)
	else:
		x = 0
	if i == K - 1 or (i >= K and (not (P[i - K] < P[smin[0]] and smax[0] == i))):
		if x != K - 1:
			r += 1
		else:
			r2 = 1
print(r + 1 if r2 else r)


import sys

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

def mapint():
	return map(int, input().split())
sys.setrecursionlimit(10 ** 9)
(N, K) = mapint()
Ps = list(mapint())

def segfunc(x, y):
	return min(x, y)

def segfunc_2(x, y):
	return max(x, y)

class SegTree:

	def __init__(self, init_val, segfunc, ide_ele):
		n = len(init_val)
		self.segfunc = segfunc
		self.ide_ele = ide_ele
		self.num = 1 << (n - 1).bit_length()
		self.tree = [ide_ele] * 2 * self.num
		for i in range(n):
			self.tree[self.num + i] = init_val[i]
		for i in range(self.num - 1, 0, -1):
			self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

	def update(self, k, x):
		k += self.num
		self.tree[k] = x
		while k > 1:
			self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
			k >>= 1

	def query(self, l, r):
		res = self.ide_ele
		l += self.num
		r += self.num
		while l < r:
			if l & 1:
				res = self.segfunc(res, self.tree[l])
				l += 1
			if r & 1:
				res = self.segfunc(res, self.tree[r - 1])
			l >>= 1
			r >>= 1
		return res
if N == K:
	print(1)
	exit()
seg_min = SegTree(Ps, segfunc, 10 ** 18)
seg_max = SegTree(Ps, segfunc_2, -1)
str_set = set()
cnt = 1
old = 10 ** 18
is_increase = [0] * N
for i in range(N):
	p = Ps[i]
	if p > old:
		cnt += 1
		is_increase[i] = cnt
	else:
		cnt = 1
		is_increase[i] = cnt
	old = p
original = 0
ans = N - K + 1
for i in range(N - K):
	mini = Ps[i]
	maxi = Ps[i + K]
	if is_increase[i + K - 1] >= K:
		original = 1
		ans -= 1
	elif seg_min.query(i, i + K + 1) == mini and seg_max.query(i, i + K + 1) == maxi:
		ans -= 1
if is_increase[-1] >= K:
	original = 1
	ans -= 1
print(ans + original)


(n, k) = map(int, input().split())
l = list(map(int, input().split()))
sc = 0
ans = n - k + 1
INF = n + 1
No = 2
while No < n:
	No *= 2
tree = [[0, 0]] * (2 * No)
for i in range(No - 1, No - 1 + n):
	tree[i] = [l[i - No + 1], l[i - No + 1]]
for i in range(No - 2, -1, -1):
	(a, b) = tree[i * 2 + 1]
	(c, d) = tree[i * 2 + 2]
	tree[i] = [max(a, c), min(b, d)]

def query(l, r):
	L = l + No - 1
	R = r + No - 1
	s = [-INF, INF]
	while L <= R:
		if R & 1:
			(a, b) = tree[R]
			(c, d) = s
			s = [max(a, c), min(b, d)]
			R -= 2
		else:
			R -= 1
		if L & 1:
			L -= 1
		else:
			(a, b) = tree[L]
			(c, d) = s
			s = [max(a, c), min(b, d)]
		L >>= 1
		R >>= 1
	return s

class unionfind:

	def __init__(self, n):
		self.n = n
		self.root = [-1] * (n + 1)
		self.rnk = [0] * (n + 1)

	def find(self, x):
		if self.root[x] < 0:
			return x
		else:
			self.root[x] = self.find(self.root[x])
			return self.root[x]

	def unite(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if x == y:
			return
		elif self.rnk[x] > self.rnk[y]:
			self.root[x] += self.root[y]
			self.root[y] = x
		else:
			self.root[y] += self.root[x]
			self.root[x] = y
			if self.rnk[x] == self.rnk[y]:
				self.rnk[y] += 1

	def same(self, x, y):
		return self.find(x) == self.find(y)

	def count(self, x):
		return -self.root[self.find(x)]
uf = unionfind(n)
s = set()
t = 1
for i in range(n - 1):
	if l[i] < l[i + 1]:
		t += 1
	else:
		t = 1
	if t >= k:
		s.add(i - k + 2)
if len(s) > 1:
	a = s.pop()
	while s:
		uf.unite(a, s.pop())
for i in range(n - k):
	(b, a) = query(i, i + k)
	if l[i] == a and l[i + k] == b:
		uf.unite(i, i + 1)
s = set()
for i in range(n - k + 1):
	s.add(uf.find(i))
print(len(s))


(n, k) = map(int, input().split())
p = tuple(map(int, input().split()))

class Seg_min:

	def __init__(self, x):
		self.ide_ele_min = 10 ** 10
		self.func = min
		self.n = len(x)
		self.num_max = 2 ** (self.n - 1).bit_length()
		self.x = [self.ide_ele_min] * 2 * self.num_max
		for (i, num) in enumerate(x, self.num_max):
			self.x[i] = num
		for i in range(self.num_max - 1, 0, -1):
			self.x[i] = self.func(self.x[i << 1], self.x[(i << 1) + 1])

	def update(self, i, x):
		i += self.num_max
		self.x[i] = x
		while x > 0:
			i = i // 2
			self.x[i] = self.func(self.x[i << 1], self.x[(i << 1) + 1])

	def query(self, i, j):
		res = self.ide_ele_min
		if i >= j:
			return res
		i += self.num_max
		j += self.num_max - 1
		while i <= j:
			if i == j:
				res = self.func(res, self.x[i])
				break
			if i & 1:
				res = self.func(res, self.x[i])
				i += 1
			if not j & 1:
				res = self.func(res, self.x[j])
				j -= 1
			i = i >> 1
			j = j >> 1
		return res

class Seg_max:

	def __init__(self, x):
		self.ide_ele_min = 10 ** 10 * -1
		self.func = max
		self.n = len(x)
		self.num_max = 2 ** (self.n - 1).bit_length()
		self.x = [self.ide_ele_min] * 2 * self.num_max
		for (i, num) in enumerate(x, self.num_max):
			self.x[i] = num
		for i in range(self.num_max - 1, 0, -1):
			self.x[i] = self.func(self.x[i << 1], self.x[(i << 1) + 1])

	def update(self, i, x):
		i += self.num_max
		self.x[i] = x
		while x > 0:
			i = i // 2
			self.x[i] = self.func(self.x[i << 1], self.x[(i << 1) + 1])

	def query(self, i, j):
		res = self.ide_ele_min
		if i >= j:
			return res
		i += self.num_max
		j += self.num_max - 1
		while i <= j:
			if i == j:
				res = self.func(res, self.x[i])
				break
			if i & 1:
				res = self.func(res, self.x[i])
				i += 1
			if not j & 1:
				res = self.func(res, self.x[j])
				j -= 1
			i = i >> 1
			j = j >> 1
		return res
seg_min = Seg_min(p)
seg_max = Seg_max(p)
natural = 0
ans = 0
head = 0
for i in range(1, n):
	if p[i] < p[i - 1]:
		head = i
	if i - head >= k - 1:
		natural = 1
		continue
	if i == k - 1:
		ans += 1
	if i < k:
		continue
	ans += 1
	left = seg_min.query(i - k, i)
	right = seg_max.query(i - k + 1, i + 1)
	if (left == p[i - k]) & (right == p[i]):
		ans -= 1
print(ans + natural)


class SegmentTree:

	def __init__(self, l, init):
		nb = bin(len(l))[2:]
		b = sum([int(d) for d in nb])
		if b == 1:
			self.end_leaves = pow(2, len(nb) - 1)
		else:
			self.end_leaves = pow(2, len(nb))
		self.tree = [init] * (self.end_leaves * 2)
		for i in range(len(l)):
			self.tree[self.end_leaves + i] = l[i]

	def stmax(self, a):
		if a >= self.end_leaves // 2:
			self.tree[a] = max(self.tree[a * 2:a * 2 + 2])
			return self.tree[a]
		else:
			self.tree[a] = max(self.stmax(a * 2), self.stmax(a * 2 + 1))
			return self.tree[a]

	def stmin(self, a):
		if a >= self.end_leaves // 2:
			self.tree[a] = min(self.tree[a * 2:a * 2 + 2])
			return self.tree[a]
		else:
			self.tree[a] = min(self.stmin(a * 2), self.stmin(a * 2 + 1))
			return self.tree[a]

	def querymax(self, l, r):
		x = l + self.end_leaves
		y = r + self.end_leaves
		tl = 0
		tr = 0
		while y - x > 1:
			if x % 2 == 1:
				tl = max(tl, self.tree[x])
				x += 1
			if y % 2 == 0:
				tr = max(self.tree[y], tr)
				y -= 1
			x >>= 1
			y >>= 1
		if y - x == 0:
			return max(tl, tr, self.tree[x])
		else:
			return max(tl, tr, self.tree[x], self.tree[y])

	def querymin(self, l, r):
		x = l + self.end_leaves
		y = r + self.end_leaves
		tl = float('inf')
		tr = float('inf')
		while y - x > 1:
			if x % 2 == 1:
				tl = min(tl, self.tree[x])
				x += 1
			if y % 2 == 0:
				tr = min(self.tree[y], tr)
				y -= 1
			x >>= 1
			y >>= 1
		if y - x == 0:
			return min(tl, tr, self.tree[x])
		else:
			return min(tl, tr, self.tree[x], self.tree[y])
from collections import deque
(N, K) = (int(x) for x in input().split())
P = list(map(int, input().split()))
d = deque(P)
st1 = SegmentTree(P, 0)
st1.stmax(1)
st2 = SegmentTree(P, float('inf'))
st2.stmin(1)
combo = 0
mono_increased = False
ans = 0
comp = -1
for i in range(K):
	temp = d.popleft()
	if temp > comp:
		combo += 1
	else:
		combo = 1
	comp = temp
if combo == K:
	mono_increased = True
else:
	ans += 1
d2 = deque(P)
for i in range(1, N - K + 1):
	temp = d.popleft()
	if temp > comp:
		if combo < K - 1:
			combo += 1
		elif combo == K - 1:
			combo += 1
			mono_increased = True
	else:
		combo = 1
	comp = temp
	t2 = d2.popleft()
	if combo < K:
		if temp < st1.querymax(i, i + K - 1):
			ans += 1
		elif t2 > st2.querymin(i, i + K - 1):
			ans += 1
if mono_increased == True:
	print(ans + 1)
else:
	print(ans)


from collections import deque
(N, K) = map(int, input().split())
a = list(map(int, input().split()))
ans = 1
c = 0
d = 0
q = deque()
p = deque()
for i in range(K):
	if len(q) == 0:
		q.append(i)
	else:
		while len(q) > 0:
			if a[q[len(q) - 1]] > a[i]:
				q.pop()
			else:
				q.append(i)
				break
		else:
			q.append(i)
	if len(p) == 0:
		p.append(i)
	else:
		while len(p) > 0:
			if a[p[len(p) - 1]] < a[i]:
				p.pop()
			else:
				p.append(i)
				break
		else:
			p.append(i)
	if len(q) == K:
		c += 1
for i in range(K, N):
	if len(q) == 0:
		q.append(i)
	else:
		flag = 0
		while len(q) > 0:
			if a[q[len(q) - 1]] > a[i]:
				q.pop()
				flag = 1
			else:
				q.append(i)
				break
		else:
			q.append(i)
		if q[0] == i - K:
			l = q.popleft()
		else:
			flag = 1
	if len(p) == 0:
		p.append(i)
	else:
		while len(p) > 0:
			if a[p[len(p) - 1]] < a[i]:
				p.pop()
			else:
				p.append(i)
				break
		else:
			p.append(i)
		if a[p[0]] > a[i]:
			flag = 1
		if p[0] == i - K:
			l = p.popleft()
	if flag == 1:
		ans += 1
	if len(q) == K and flag == 1:
		c += 1
if c > 1:
	ans -= c - 1
print(ans)


def main():

	def update(k, x):
		k += N0 - 1
		data_min[k] = data_max[k] = x
		while k >= 0:
			k = (k - 1) // 2
			(a, b) = (data_min[2 * k + 1], data_min[2 * k + 2])
			data_min[k] = a if a < b else b
			(a, b) = (data_max[2 * k + 1], data_max[2 * k + 2])
			data_max[k] = a if a > b else b

	def query_min(l, r):
		(L, R) = (l + N0, r + N0)
		s = INF
		while L < R:
			if R & 1:
				R -= 1
				t = data_min[R - 1]
				if t < s:
					s = t
			if L & 1:
				t = data_min[L - 1]
				if t < s:
					s = t
				L += 1
			L //= 2
			R //= 2
		return s

	def query_max(l, r):
		(L, R) = (l + N0, r + N0)
		s = 0
		while L < R:
			if R & 1:
				R -= 1
				t = data_max[R - 1]
				if t > s:
					s = t
			if L & 1:
				t = data_max[L - 1]
				if t > s:
					s = t
				L += 1
			L //= 2
			R //= 2
		return s
	(n, k, *p) = map(int, open(0).read().split())
	N0 = 2 ** (n - 1).bit_length()
	INF = 10 ** 18
	data_min = [INF] * 2 * N0
	data_max = [0] * 2 * N0
	c = [0]
	for (a, b) in zip(p, p[1:]):
		c += (c[-1] + (a < b),)
	(*c, f) = [b - a == k - 1 for (a, b) in zip(c, c[k - 1:])]
	x = not f
	for (i, q) in enumerate(p):
		update(i, q)
	for (i, (a, b, c)) in enumerate(zip(p, p[k:], c)):
		f |= c
		if not c and (a != query_min(i, i + k) or b != query_max(i + 1, i + k + 1)):
			x += 1
	print(x + f)
main()


from operator import add
import sys
input = sys.stdin.readline

class SegTree:

	def __init__(self, N, e, operator_func=add):
		self.e = e
		self.size = N
		self.node = [self.e] * (2 * N)
		self.operator_func = operator_func

	def set_list(self, l):
		for i in range(self.size):
			self.node[i + self.size - 1] = l[i]
		for i in range(self.size - 1)[::-1]:
			self.node[i] = self.operator_func(self.node[2 * i + 1], self.node[2 * i + 2])

	def update(self, k, x):
		k += self.size - 1
		self.node[k] = x
		while k >= 0:
			k = (k - 1) // 2
			self.node[k] = self.operator_func(self.node[2 * k + 1], self.node[2 * k + 2])

	def get(self, l, r):
		x = self.e
		l += self.size
		r += self.size
		while l < r:
			if l & 1:
				x = self.operator_func(x, self.node[l - 1])
				l += 1
			if r & 1:
				r -= 1
				x = self.operator_func(x, self.node[r - 1])
			l >>= 1
			r >>= 1
		return x

def solve():
	(N, K) = map(int, input().split())
	P = list(map(int, input().split()))
	tree = SegTree(N, 10 ** 12, min)
	tree_min = SegTree(N, 10 ** 12, min)
	tree_max = SegTree(N, -10 ** 12, max)
	tree_min.set_list(P)
	tree_max.set_list(P)
	tree.set_list([P[i] - P[i - 1] if i else P[i] for i in range(N)])
	f = lambda l, r: tree.get(l + 1, r) >= 0
	ans = N - K + 1
	isOrig = 0
	for i in range(N - K):
		if f(i, i + K):
			ans -= 1
			isOrig = 1
		elif tree_min.get(i, i + 1 + K) == P[i] and tree_max.get(i, i + 1 + K) == P[i + K]:
			ans -= 1
	if f(N - K, N):
		ans -= 1
		isOrig = 1
	ans += isOrig
	print(ans)
solve()


class MinSlideWindow:

	def __init__(self, p):
		self.pos_list = []
		self.val_list = p
		self.start_idx = 0

	def put(self, pos):
		val = self.val_list[pos]
		while len(self.pos_list) > self.start_idx:
			pos1 = self.pos_list[-1]
			val1 = self.val_list[pos1]
			if val1 >= val:
				del self.pos_list[-1]
			else:
				break
		self.pos_list.append(pos)

	def get(self, pos):
		while len(self.pos_list) > self.start_idx:
			pos1 = self.pos_list[self.start_idx]
			if pos1 <= pos:
				self.start_idx += 1
			else:
				break

	def min(self):
		pos1 = self.pos_list[self.start_idx]
		val1 = self.val_list[pos1]
		return val1

class MaxSlideWindow:

	def __init__(self, p):
		self.pos_list = []
		self.val_list = p
		self.start_idx = 0

	def put(self, pos):
		val = self.val_list[pos]
		while len(self.pos_list) > self.start_idx:
			pos1 = self.pos_list[-1]
			val1 = self.val_list[pos1]
			if val1 <= val:
				del self.pos_list[-1]
			else:
				break
		self.pos_list.append(pos)

	def get(self, pos):
		while len(self.pos_list) > self.start_idx:
			pos1 = self.pos_list[self.start_idx]
			if pos1 <= pos:
				del self.pos_list[self.start_idx]
			else:
				break

	def max(self):
		pos1 = self.pos_list[self.start_idx]
		val1 = self.val_list[pos1]
		return val1
s = input().split(' ')
n = int(s[0])
k = int(s[1])
sp = input().split(' ')
p = [int(pstr) for pstr in sp]
num = 1
ident = True
rv_pos = -1
minw = MinSlideWindow(p)
maxw = MaxSlideWindow(p)
for i in range(k - 1):
	if p[i] > p[i + 1]:
		rv_pos = i
		ident = False
for i in range(k - 1):
	minw.put(i)
	maxw.put(i)
for i in range(1, n - k + 1):
	maxw.put(i + k - 2)
	minw.put(i + k - 2)
	maxw.get(i - 1)
	minw.get(i - 1)
	if p[i + k - 2] > p[i + k - 1]:
		rv_pos = i + k - 2
	if rv_pos < i:
		if not ident:
			ident = True
			num += 1
		continue
	if p[i - 1] > minw.min() or p[i + k - 1] < maxw.max():
		num += 1
print(num)


from collections import deque
(n, k) = map(int, input().split())
p = list(map(int, input().split())) + [1000000]
p1 = [0] * n
pmin = [0] * (n + 1)
pmax = [0] * (n + 1)
cnt = 0
for i in range(n - 1):
	if p[i] < p[i + 1]:
		cnt += 1
	else:
		cnt = 0
	p1[i + 1] = cnt
d = deque()
d.append(0)
for i in range(1, k + 1):
	if p[d[-1]] < p[i]:
		d.append(i)
	else:
		try:
			while p[d[-1]] > p[i]:
				d.pop()
		except:
			pass
		d.append(i)
pmin[k] = p[d[0]]
for i in range(k + 1, n):
	if d[0] == i - (k + 1):
		d.popleft()
	if p[d[-1]] < p[i]:
		d.append(i)
	else:
		try:
			while p[d[-1]] > p[i]:
				d.pop()
		except:
			pass
		d.append(i)
	pmin[i] = p[d[0]]
dd = deque()
dd.append(0)
for i in range(1, k + 1):
	if p[dd[-1]] > p[i]:
		dd.append(i)
	else:
		try:
			while p[dd[-1]] < p[i]:
				dd.pop()
		except:
			pass
		dd.append(i)
pmax[k] = p[dd[0]]
for i in range(k + 1, n):
	if dd[0] == i - (k + 1):
		dd.popleft()
	if p[dd[-1]] > p[i]:
		dd.append(i)
	else:
		try:
			while p[dd[-1]] < p[i]:
				dd.pop()
		except:
			pass
		dd.append(i)
	pmax[i] = p[dd[0]]
ans = n - k + 1
f = 1
ff = [0] * n
for i in range(n):
	if p1[i] >= k - 1:
		ff[i] = 1
		if f == 0:
			ans -= 1
		else:
			f = 0
for i in range(n - k):
	if p[i] == pmin[i + k] and p[i + k] == pmax[i + k] and (ff[i + k] == 0):
		ans -= 1
print(ans)


import heapq
(N, K) = map(int, input().split())
P = [int(p) for p in input().split()]
h = []
H = []
for i in range(K):
	heapq.heappush(h, (P[i], i))
	heapq.heappush(H, (-P[i], i))
ans = 1
for i in range(N - K):
	while h[0][1] < i:
		heapq.heappop(h)
	while H[0][1] < i:
		heapq.heappop(H)
	heapq.heappush(h, (P[i + K], i + K))
	heapq.heappush(H, (-P[i + K], i + K))
	if h[0][0] == P[i] and -H[0][0] == P[i + K]:
		continue
	ans += 1
f = 0
cnt = 1
for i in range(N - 1):
	if P[i] < P[i + 1]:
		cnt += 1
	else:
		if cnt >= K and f == 1:
			ans -= 1
		elif cnt >= K and f == 0:
			f = 1
		cnt = 1
if cnt >= K and f == 1:
	ans -= 1
print(ans)


(N, K) = map(int, input().split())
P = list(map(int, input().split()))
LIS = [1 for i in range(0, N)]
s = 0
t = 1
while N > t:
	if P[t] >= P[t - 1]:
		t += 1
		if t == N:
			ans = N - s
			while t > s:
				LIS[s] = ans
				s += 1
				ans -= 1
	else:
		ans = t - s
		while t > s:
			LIS[s] = ans
			s += 1
			ans -= 1
		t += 1
nochange = set([])
for i in range(0, N - K + 1):
	if LIS[i] >= K:
		nochange.add(i)
n = N

def segfunc(x, y):
	return (min(x[0], y[0]), max(x[1], y[1]))

def init(init_val):
	for i in range(n):
		seg[i + num - 1] = init_val[i]
	for i in range(num - 2, -1, -1):
		seg[i] = segfunc(seg[2 * i + 1], seg[2 * i + 2])

def update(k, x):
	k += num - 1
	seg[k] = x
	while k:
		k = (k - 1) // 2
		seg[k] = segfunc(seg[k * 2 + 1], seg[k * 2 + 2])

def query(p, q):
	if q <= p:
		return ide_ele
	p += num - 1
	q += num - 2
	res = ide_ele
	while q - p > 1:
		if p & 1 == 0:
			res = segfunc(res, seg[p])
		if q & 1 == 1:
			res = segfunc(res, seg[q])
			q -= 1
		p = p // 2
		q = (q - 1) // 2
	if p == q:
		res = segfunc(res, seg[p])
	else:
		res = segfunc(segfunc(res, seg[p]), seg[q])
	return res
ide_ele = (10 ** 20, 0)
num = 2 ** (n - 1).bit_length()
seg = [ide_ele] * 2 * num
PP = [(P[i], P[i]) for i in range(0, N)]
init(PP)
ans = []
if 0 not in nochange:
	ans.append(0)
for i in range(1, N - K + 1):
	if i in nochange:
		continue
	else:
		M = query(i, i + K)[1]
		m = query(i - 1, i - 1 + K)[0]
		if m == P[i - 1] and M == P[i + K - 1]:
			continue
		else:
			ans.append(i)
if nochange:
	print(len(ans) + 1)
else:
	print(len(ans))


(N, K) = map(int, input().split())
P = [float('inf')] + list(map(int, input().split())) + [float('inf')]
A = [0] * N
B = [0] * (N + 2)
hoge = 1
for i in range(1, N):
	if P[i] < P[i + 1]:
		hoge += 1
	else:
		hoge = 1
	if hoge >= K:
		B[i - K + 2] = 1
for i in range(1, N + 1):
	A[P[i]] = i
(minL, minR, maxL, maxR) = ([i - 1 for i in range(N + 2)], [i + 1 for i in range(N + 2)], [i - 1 for i in range(N + 2)], [i + 1 for i in range(N + 2)])
for i in range(N):
	m = A[i]
	(x, y) = (maxL[m], maxR[m])
	maxL[y] = x
	maxR[x] = y
(P[0], P[-1]) = (-1, -1)
for i in range(N - 1, -1, -1):
	m = A[i]
	(x, y) = (minL[m], minR[m])
	minL[y] = x
	minR[x] = y
ans = 1
for i in range(1, N - K + 1):
	(L, R) = (i, i + K)
	if B[i + 1] == 0 and (minR[L] <= R or maxL[R] >= L):
		ans += 1
if sum(B) and B[1] == 0:
	ans += 1
print(ans)


import sys, queue, math, copy, itertools, bisect, collections, heapq

def main():
	LI = lambda : [int(x) for x in sys.stdin.readline().split()]
	(N, K) = LI()
	P = LI()
	N0 = 2 ** N.bit_length()
	st1 = [0] * (2 * N0)
	st2 = [0] * (2 * N0)
	i = N0 - 1
	for x in P:
		st1[i] = st2[i] = x
		i += 1
	for i in range(N0 - 2, -1, -1):
		st1[i] = max(st1[i * 2 + 1], st1[i * 2 + 2])
		st2[i] = min(st2[i * 2 + 1], st2[i * 2 + 2])

	def query_max(l, r):
		L = l + N0
		R = r + N0
		ret = 0
		while L < R:
			if L % 2:
				ret = max(ret, st1[L - 1])
				L += 1
			if R % 2:
				R -= 1
				ret = max(ret, st1[R - 1])
			L //= 2
			R //= 2
		return ret

	def query_min(l, r):
		L = l + N0
		R = r + N0
		ret = N + 1
		while L < R:
			if L % 2:
				ret = min(ret, st2[L - 1])
				L += 1
			if R % 2:
				R -= 1
				ret = min(ret, st2[R - 1])
			L //= 2
			R //= 2
		return ret
	ans = 0
	cnt = 0
	flg = 0
	bp = N
	for i in range(N):
		if P[i] > bp:
			cnt += 1
		else:
			cnt = 0
		bp = P[i]
		if i < K - 1:
			continue
		if cnt >= K - 1:
			flg = 1
		elif i >= K and query_min(i - K, i) == P[i - K] and (query_max(i - K + 1, i + 1) == P[i]):
			pass
		else:
			ans += 1
	print(ans + flg)
main()


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

class BITmax:
	ini = 0

	def __init__(s, num):
		s.N = 1
		while s.N <= num:
			s.N *= 2
		s.T = [s.ini] * s.N

	def set(s, L):
		for i in range(len(L)):
			s.update(i, L[i])

	def update(s, t, x):
		k = t
		s.T[k - 1] = max(s.T[k - 1], x)
		k += k & -k
		while k <= s.N:
			s.T[k - 1] = max(s.T[k - 1], x)
			k += k & -k

	def getV(s, x):
		ans = s.T[x - 1]
		x -= x & -x
		while x != 0:
			ans = max(ans, s.T[x - 1])
			x -= x & -x
		return ans

class BITmin:
	ini = N

	def __init__(s, num):
		s.N = 1
		while s.N <= num:
			s.N *= 2
		s.T = [s.ini] * s.N

	def set(s, L):
		for i in range(len(L)):
			s.update(i, L[i])

	def update(s, t, x):
		k = t
		s.T[k - 1] = min(s.T[k - 1], x)
		k += k & -k
		while k <= s.N:
			s.T[k - 1] = min(s.T[k - 1], x)
			k += k & -k

	def getV(s, x):
		ans = s.T[x - 1]
		x -= x & -x
		while x != 0:
			ans = min(ans, s.T[x - 1])
			x -= x & -x
		return ans
MA = BITmax(N)
MI = BITmin(N)
La = [0] * N
Li = [0] * N
for i in range(K - 1):
	t = N - i
	MA.update(t, P[t - 1])
	MI.update(t, P[t - 1])
for i in range(K - 2, N):
	t = N - i
	MA.update(t, P[t - 1])
	MI.update(t, P[t - 1])
	La[t - 1] = MA.getV(t + K - 2)
	Li[t - 1] = MI.getV(t + K - 2)
T = [0] * N
cnt = 0
t = 0
for i in range(1, N):
	if P[i] > P[i - 1]:
		cnt += 1
		if cnt >= K - 1:
			T[i - K + 1] = 1
			t += 1
	else:
		cnt = 0
if t != 0:
	t -= 1
for i in range(N - K):
	if T[i] == 1:
		continue
	if Li[i + 1] > P[i] and La[i + 1] < P[i + K]:
		t += 1
print(N - K - t + 1)


class BIT:

	def __init__(self, n):
		self.N = n
		self.n = 1 << n.bit_length()
		self.data = [0] * (self.n + 1)
		self.num = 0

	def sum(self, i):
		s = 0
		while i > 0:
			s += self.data[i]
			i -= i & -i
		return s

	def add(self, i, x):
		while i <= self.n:
			self.data[i] += x
			i += i & -i
		self.num += 1

	def search(self, value):
		if value < 1:
			return 0
		if value > self.num:
			return self.N + 1
		(x, sx) = (0, 0)
		step = self.n
		while step:
			y = x + step
			sy = sx + self.data[y]
			if sy < value:
				(x, sx) = (y, sy)
			step >>= 1
		return x + 1

class UnionFind(object):

	def __init__(self, size):
		self.parent = [i for i in range(size)]
		self.rank = [0 for _ in range(size)]

	def find(self, x):
		if self.parent[x] == x:
			return x
		else:
			return self.find(self.parent[x])

	def unite(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if x == y:
			return
		if self.rank[x] < self.rank[y]:
			self.parent[x] = y
		else:
			self.parent[y] = x
			if self.rank[x] == self.rank[y]:
				self.rank[x] += 1

	def same(self, x, y):
		return self.find(x) == self.find(y)
from collections import deque
(N, K) = map(int, input().split())
P = list(map(int, input().split()))
B = BIT(N)
U = UnionFind(N)
ans = N - K + 1
for i in range(K):
	B.add(P[i] + 1, 1)
for i in range(1, N - K + 1):
	m = B.search(1)
	M = B.search(K)
	if P[i - 1] + 1 == m and P[i + K - 1] + 1 > M:
		U.unite(i - 1, i)
	B.add(P[i - 1] + 1, -1)
	B.add(P[i + K - 1] + 1, 1)
(s, l) = (0, 1)
List = []
for i in range(1, N):
	if P[i - 1] < P[i]:
		l += 1
	else:
		if l >= K:
			List.append(s)
		l = 1
		s = i
if l >= K:
	List.append(s)
if len(List) > 0:
	s = List[0]
	for i in List[1:]:
		U.unite(s, i)
ans = 0
for i in range(N):
	if U.parent[i] == i:
		ans += 1
print(ans - K + 1)


from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from functools import reduce
sys.setrecursionlimit(2147483647)
INF = 10 ** 18

def LI():
	return list(map(int, sys.stdin.buffer.readline().split()))

def I():
	return int(sys.stdin.buffer.readline())

def LS():
	return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()

def S():
	return sys.stdin.buffer.readline().rstrip().decode('utf-8')

def IR(n):
	return [I() for i in range(n)]

def LIR(n):
	return [LI() for i in range(n)]

def SR(n):
	return [S() for i in range(n)]

def LSR(n):
	return [LS() for i in range(n)]

def SRL(n):
	return [list(S()) for i in range(n)]

def MSRL(n):
	return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007

class SegmentTree:

	def __init__(self, init_val, ide_ele, op):
		n = len(init_val)
		self.num = 2 ** (n - 1).bit_length()
		self.seg = [ide_ele] * 2 * self.num
		self.ide_ele = ide_ele
		self.op = op
		for i in range(n):
			self.seg[i + self.num - 1] = init_val[i]
		for i in range(self.num - 2, -1, -1):
			self.seg[i] = self.op(self.seg[2 * i + 1], self.seg[2 * i + 2])

	def update(self, k, x):
		k += self.num - 1
		self.seg[k] = x
		while k:
			k = (k - 1) // 2
			self.seg[k] = self.op(self.seg[k * 2 + 1], self.seg[k * 2 + 2])

	def query(self, p, q):
		if q <= p:
			return self.ide_ele
		p += self.num - 1
		q += self.num - 2
		res = self.ide_ele
		while q - p > 1:
			if p & 1 == 0:
				res = self.op(res, self.seg[p])
			if q & 1 == 1:
				res = self.op(res, self.seg[q])
			p = p // 2
			q = (q - 2) // 2
		if p == q:
			res = self.op(res, self.seg[p])
		else:
			res = self.op(self.seg[p], self.op(res, self.seg[q]))
		return res
(n, k) = LI()
L = LI()
min_ST = SegmentTree(L, INF, min)
max_ST = SegmentTree(L, -INF, max)
cnt = 1
for i in range(n - k):
	if min_ST.query(i, i + k) == L[i] and max_ST.query(i + 1, i + k + 1) == L[i + k]:
		continue
	else:
		cnt += 1
ret = -INF
increasing_block_num = 0
max_len = 0
for j in range(n):
	if L[j] >= ret:
		max_len += 1
	else:
		if max_len >= k:
			increasing_block_num += 1
		max_len = 1
	ret = L[j]
if max_len >= k:
	increasing_block_num += 1
if increasing_block_num:
	print(cnt - (increasing_block_num - 1))
else:
	print(cnt)


import sys
sys.setrecursionlimit(2147483647)
INF = float('inf')
MOD = 10 ** 9 + 7
input = lambda : sys.stdin.readline().rstrip()

class SparseTable(object):

	def __init__(self, A):
		n = len(A)
		logn = max(0, (n - 1).bit_length())
		maxtable = [[0] * n for _ in range(logn)]
		maxtable[0] = A[:]
		mintable = [[0] * n for _ in range(logn)]
		mintable[0] = A[:]
		from itertools import product
		for (i, k) in product(range(1, logn), range(n)):
			if k + (1 << i - 1) >= n:
				maxtable[i][k] = maxtable[i - 1][k]
				mintable[i][k] = mintable[i - 1][k]
			else:
				maxtable[i][k] = max(maxtable[i - 1][k], maxtable[i - 1][k + (1 << i - 1)])
				mintable[i][k] = min(mintable[i - 1][k], mintable[i - 1][k + (1 << i - 1)])
		self.__n = n
		self.__maxtable = maxtable
		self.__mintable = mintable

	def max(self, l, r):
		n = self.__n
		assert 0 <= l < r <= n
		i = max(0, (r - l - 1).bit_length() - 1)
		maxtable = self.__maxtable
		return max(maxtable[i][l], maxtable[i][r - (1 << i)])

	def min(self, l, r):
		n = self.__n
		assert 0 <= l < r <= n
		i = max(0, (r - l - 1).bit_length() - 1)
		mintable = self.__mintable
		return min(mintable[i][l], mintable[i][r - (1 << i)])

def resolve():
	(n, k) = map(int, input().split())
	P = list(map(int, input().split()))
	table = SparseTable(P)
	ans = n - k + 1
	for i in range(n - k):
		m = table.min(i, i + k)
		M = table.max(i + 1, i + 1 + k)
		if m == P[i] and M == P[i + k]:
			ans -= 1
	cnt = 0
	num = 0
	P.append(-1)
	for i in range(n):
		if P[i + 1] > P[i]:
			cnt += 1
		else:
			num += cnt >= k - 1
			cnt = 0
	ans -= max(num - 1, 0)
	print(ans)
resolve()


import sys
from itertools import accumulate

class Segtree:

	def __init__(self, A, intv, initialize=True, segf=max):
		self.N = len(A)
		self.N0 = 2 ** (self.N - 1).bit_length()
		self.intv = intv
		self.segf = segf
		if initialize:
			self.data = [intv] * self.N0 + A + [intv] * (self.N0 - self.N)
			for i in range(self.N0 - 1, 0, -1):
				self.data[i] = self.segf(self.data[2 * i], self.data[2 * i + 1])
		else:
			self.data = [intv] * (2 * self.N0)

	def update(self, k, x):
		k += self.N0
		self.data[k] = x
		while k > 0:
			k = k >> 1
			self.data[k] = self.segf(self.data[2 * k], self.data[2 * k + 1])

	def query(self, l, r):
		(L, R) = (l + self.N0, r + self.N0)
		s = self.intv
		while L < R:
			if R & 1:
				R -= 1
				s = self.segf(s, self.data[R])
			if L & 1:
				s = self.segf(s, self.data[L])
				L += 1
			L >>= 1
			R >>= 1
		return s

	def binsearch(self, l, r, check, reverse=False):
		(L, R) = (l + self.N0, r + self.N0)
		(SL, SR) = ([], [])
		while L < R:
			if R & 1:
				R -= 1
				SR.append(R)
			if L & 1:
				SL.append(L)
				L += 1
			L >>= 1
			R >>= 1
		if reverse:
			for idx in SR + SL[::-1]:
				if check(self.data[idx]):
					break
			else:
				return -1
			while idx < self.N0:
				if check(self.data[2 * idx + 1]):
					idx = 2 * idx + 1
				else:
					idx = 2 * idx
			return idx
		else:
			for idx in SL + SR[::-1]:
				if check(self.data[idx]):
					break
			else:
				return -1
			while idx < self.N0:
				if check(self.data[2 * idx]):
					idx = 2 * idx
				else:
					idx = 2 * idx + 1
			return idx
readline = sys.stdin.readline
(N, K) = map(int, readline().split())
P = list(map(int, readline().split()))
STmax = Segtree(P, 0, True, max)
STmin = Segtree(P, 10 ** 9, True, min)
ans = N - K + 1
upper = [0] * (N - 1)
for i in range(N - 1):
	if P[i] > P[i + 1]:
		upper[i] = 1
upper = list(accumulate(upper)) + [0]
cnt = 0
for i in range(N - K):
	if upper[i + K - 2] == upper[i - 1]:
		cnt += 1
	elif P[i + K] == STmax.query(i + 1, i + K + 1) and P[i] == STmin.query(i, i + K):
		ans -= 1
if upper[N - 2] == upper[N - K - 1]:
	cnt += 1
print(ans - max(0, cnt - 1))


class SegTree:

	def __init__(self, size, func, sta):
		self.n = size
		self.size = 1 << size.bit_length()
		self.func = func
		self.sta = sta
		self.tree = [sta] * (2 * self.size)

	def build(self, list):
		for (i, x) in enumerate(list, self.size):
			self.tree[i] = x
		for i in range(self.size - 1, 0, -1):
			self.tree[i] = self.func(self.tree[i << 1], self.tree[i << 1 | 1])

	def set(self, i, x):
		i += self.size
		self.tree[i] = x
		while i > 1:
			i >>= 1
			self.tree[i] = self.func(self.tree[i << 1], self.tree[i << 1 | 1])

	def get(self, l, r):
		l += self.size
		r += self.size
		res = self.sta
		while l < r:
			if l & 1:
				res = self.func(self.tree[l], res)
				l += 1
			if r & 1:
				res = self.func(self.tree[r - 1], res)
			l >>= 1
			r >>= 1
		return res
(n, k) = map(int, input().split())
p = list(map(int, input().split()))
segmin = SegTree(n, min, 10 ** 18)
segmax = SegTree(n, max, -1)
segmin.build(p)
segmax.build(p)
count = [1] * n
for i in range(1, n):
	if p[i] > p[i - 1]:
		count[i] = count[i - 1] + 1
if n == k or max(count) == n:
	print(1)
	exit()
ans = 1
check = False
if count[k - 1] == k:
	check = True
for i in range(k, n):
	if count[i] >= k:
		if check:
			continue
		else:
			check = True
			ans += 1
			continue
	elif segmin.get(i - k, i + 1) == p[i - k] and segmax.get(i - k, i + 1) == p[i]:
		continue
	ans += 1
print(ans)


class SparseTableMAX:

	def __init__(self, array, n):
		self.row_size = n.bit_length()
		self.log_table = [0] * (n + 1)
		for i in range(2, n + 1):
			self.log_table[i] = self.log_table[i // 2] + 1
		self.sparse_table = [[0] * n for _ in range(self.row_size)]
		for i in range(n):
			self.sparse_table[0][i] = array[i]
		for row in range(1, self.row_size):
			for i in range(n - (1 << row) + 1):
				self.sparse_table[row][i] = self._merge(self.sparse_table[row - 1][i], self.sparse_table[row - 1][i + (1 << row - 1)])

	def _merge(self, num1, num2):
		return max(num1, num2)

	def query(self, l, r):
		if r == l:
			return None
		row = self.log_table[r - l]
		return self._merge(self.sparse_table[row][l], self.sparse_table[row][r - (1 << row)])

class SparseTableMIN:

	def __init__(self, array, n):
		self.row_size = n.bit_length()
		self.log_table = [0] * (n + 1)
		for i in range(2, n + 1):
			self.log_table[i] = self.log_table[i // 2] + 1
		self.sparse_table = [[0] * n for _ in range(self.row_size)]
		for i in range(n):
			self.sparse_table[0][i] = array[i]
		for row in range(1, self.row_size):
			for i in range(n - (1 << row) + 1):
				self.sparse_table[row][i] = self._merge(self.sparse_table[row - 1][i], self.sparse_table[row - 1][i + (1 << row - 1)])

	def _merge(self, num1, num2):
		return min(num1, num2)

	def query(self, l, r):
		if r == l:
			return None
		row = self.log_table[r - l]
		return self._merge(self.sparse_table[row][l], self.sparse_table[row][r - (1 << row)])
(n, k) = map(int, input().split())
a = list(map(int, input().split()))
max_st = SparseTableMAX(a, n)
min_st = SparseTableMIN(a, n)
ans = 0
for i in range(1, n - k + 1):
	l = a[i - 1]
	r = a[i + k - 1]
	min_ = min_st.query(i - 1, i - 1 + k)
	max_ = max_st.query(i, i + k)
	if l != min_ or r != max_:
		ans += 1
tmp = 0
cnt = 0
tmp_ans = 0
l = -1
for i in range(1, n):
	if a[i - 1] > a[i]:
		tmp = i
	if i >= k - 1 and tmp <= i - k + 1:
		if i - l > 1:
			cnt += 1
		l = i
ans += 1 - max(cnt - 1, 0)
print(ans)


class RangeMinimumQuery:

	def __init__(self, n, func=min, inf=float('inf')):
		self.n0 = 2 ** (n - 1).bit_length()
		self.op = func
		self.inf = inf
		self.data = [self.inf] * (2 * self.n0 - 1)

	def query(self, l, r):
		l += self.n0
		r += self.n0
		res = self.inf
		while l < r:
			if r & 1:
				r -= 1
				res = self.op(res, self.data[r - 1])
			if l & 1:
				res = self.op(res, self.data[l - 1])
				l += 1
			l >>= 1
			r >>= 1
		return res

	def update(self, i, x):
		i += self.n0 - 1
		self.data[i] = x
		while i + 1:
			i = ~-i // 2
			self.data[i] = self.op(self.data[2 * i + 1], self.data[2 * i + 2])
(n, k) = map(int, input().split())
p = list(map(int, input().split()))
RminQ = RangeMinimumQuery(n)
RmaxQ = RangeMinimumQuery(n, func=max, inf=0)
for (i, pi) in enumerate(p):
	RminQ.update(i, pi)
	RmaxQ.update(i, pi)
a = [1]
for i in range(n - 1):
	if p[i] < p[i + 1]:
		a.append(a[-1] + 1)
	else:
		a.append(1)
ans = n - k + 1
flag = a[k - 1] == k
for i in range(k, n):
	if p[i] > RmaxQ.query(i - k + 1, i) and p[i - k] < RminQ.query(i - k + 1, i) or (flag and a[i] >= k):
		ans -= 1
	if not flag and a[i] >= k:
		flag = True
print(ans)


import sys
input = sys.stdin.readline
(N, K) = map(int, input().split())
A = list(map(int, input().split()))
seg_el = 1 << N.bit_length()
SEG = [1 << 30] * (2 * seg_el)
for i in range(N):
	SEG[i + seg_el] = A[i]
for i in range(seg_el - 1, 0, -1):
	SEG[i] = min(SEG[i * 2], SEG[i * 2 + 1])

def update(n, x, seg_el):
	i = n + seg_el
	SEG[i] = x
	i >>= 1
	while i != 0:
		SEG[i] = min(SEG[i * 2], SEG[i * 2 + 1])
		i >>= 1

def getvalues(l, r):
	L = l + seg_el
	R = r + seg_el
	ANS = 1 << 30
	while L < R:
		if L & 1:
			ANS = min(ANS, SEG[L])
			L += 1
		if R & 1:
			R -= 1
			ANS = min(ANS, SEG[R])
		L >>= 1
		R >>= 1
	return ANS
SEG2 = [1 << 30] * (2 * seg_el)
for i in range(N):
	SEG2[i + seg_el] = A[i]
for i in range(seg_el - 1, 0, -1):
	SEG2[i] = max(SEG2[i * 2], SEG2[i * 2 + 1])

def update2(n, x, seg_el):
	i = n + seg_el
	SEG2[i] = x
	i >>= 1
	while i != 0:
		SEG2[i] = max(SEG2[i * 2], SEG2[i * 2 + 1])
		i >>= 1

def getvalues2(l, r):
	L = l + seg_el
	R = r + seg_el
	ANS = -1
	while L < R:
		if L & 1:
			ANS = max(ANS, SEG2[L])
			L += 1
		if R & 1:
			R -= 1
			ANS = max(ANS, SEG2[R])
		L >>= 1
		R >>= 1
	return ANS
Group = [i for i in range(N - K + 1)]

def find(x):
	if Group[x] == -1:
		return -1
	while Group[x] != x:
		x = Group[x]
	return x

def Union(x, y):
	if find(x) != find(y):
		Group[find(y)] = Group[find(x)] = min(find(y), find(x))
count = 0
for i in range(1, N):
	if A[i] > A[i - 1]:
		count += 1
	else:
		count = 0
	if count >= K - 1:
		Group[i - K + 1] = -1
for i in range(N - K):
	if A[i] < getvalues(i + 1, i + K) < getvalues2(i + 1, i + K) < A[i + K]:
		Union(i, i + 1)
B = [find(x) for x in range(N - K + 1)]
print(len(set(B)))


(n, k) = list(map(int, input().split()))
xs = list(map(int, input().split()))
from collections import deque

def slide_max(k, l):
	(rs, rrs) = ([], set())
	dq = deque()
	for (i, x) in enumerate(l):
		while True:
			if not len(dq):
				dq.append(i)
				break
			lxi = dq[-1]
			if x < l[lxi]:
				dq.append(i)
				break
			dq.pop()
		if i + 1 < k:
			continue
		sxi = dq[0]
		rs.append(l[sxi])
		if sxi == i + 1 - k:
			dq.popleft()
	return rs

def slide_min(k, l):
	rs = []
	rrs = set()
	dq = deque()
	for (i, x) in enumerate(l):
		while True:
			if not len(dq):
				dq.append(i)
				break
			lxi = dq[-1]
			if x > l[lxi]:
				dq.append(i)
				break
			dq.pop()
		if i + 1 < k:
			continue
		if len(dq) == k:
			rrs.add(i + 1 - k)
		sxi = dq[0]
		rs.append(l[sxi])
		if sxi == i + 1 - k:
			dq.popleft()
	return (rs, rrs)
(maxs, (mins, ns)) = (slide_max(k, xs), slide_min(k, xs))
r = 1
for (i, (s, x)) in enumerate(zip(xs, xs[k:])):
	if (x != maxs[i + 1] or s != mins[i]) and i + 1 not in ns:
		r += 1
if 0 not in ns and len(ns) > 0:
	r += 1
print(r)


import sys
sys.setrecursionlimit(10 ** 8)
stdin = sys.stdin

def ni():
	return int(ns())

def na():
	return list(map(int, stdin.readline().split()))

def naa(N):
	return [na() for _ in range(N)]

def ns():
	return stdin.readline().rstrip()

class SegmentTreeRMQ(object):

	def __init__(self, size, value):
		self.len = 1 << size.bit_length()
		self.array = [value] * (2 * self.len)

	def update(self, i, x):
		i += self.len
		while i > 0:
			self.array[i] = min(self.array[i], x)
			i >>= 1

	def get(self, i):
		return self.array[i + self.len]

	def get_minimum(self, l, r):
		L = l + self.len
		R = r + self.len
		ANS = 1 << 30
		while L < R:
			if L & 1:
				ANS = min(ANS, self.array[L])
				L += 1
			if R & 1:
				R -= 1
				ANS = min(ANS, self.array[R])
			L >>= 1
			R >>= 1
		return ANS
(N, K) = na()
P = na()
if N == K or N == 2:
	print(1)
	exit()
min_tree = SegmentTreeRMQ(N, N)
max_tree = SegmentTreeRMQ(N, 1)
for (i, p) in enumerate(P):
	min_tree.update(i, p)
	max_tree.update(i, -p)
no_change = [0] * (N - K + 1)
last = -1
for i in range(N):
	if i - last >= K:
		no_change[i - K + 1] = 1
	if i == N - 1:
		break
	if P[i] > P[i + 1]:
		last = i
ans = 1
no_count = 0
for i in range(N - K):
	if P[i] > min_tree.get_minimum(i + 1, i + K + 1) or -P[i + K] > max_tree.get_minimum(i + 1, i + K + 1):
		ans += 1
		if no_change[i] == 1:
			no_count += 1
	if i == N - K - 1 and no_change[N - K] == 1:
		no_count += 1
print(ans - max(0, no_count - 1))


import sys
input = sys.stdin.readline
from heapq import heapify, heappop, heappush

def main():
	(N, K) = map(int, input().split())
	P = list(map(int, input().split()))
	ans = 0
	now = -1
	cnt = 1
	CNT = [0] * N
	for i in range(N - 1, -1, -1):
		p = P[i]
		if p < now:
			cnt += 1
		else:
			cnt = 1
		now = p
		if cnt >= K:
			CNT[i] = 1
	if sum(CNT) > 0:
		ans = 1
	for i in range(K - 1):
		if P[i] > P[i + 1]:
			ans += 1
			break
	Max = [-P[i] for i in range(K)]
	Min = [P[i] for i in range(K)]
	heapify(Max)
	heapify(Min)
	C = [0] * N
	for i in range(K, N):
		while C[Min[0]] == 1:
			heappop(Min)
		while C[-Max[0]] == 1 or Max[0] == -P[i - K]:
			heappop(Max)
		if CNT[i + 1 - K] == 1:
			pass
		elif P[i - K] == Min[0] and P[i] > -Max[0]:
			pass
		else:
			ans += 1
		C[P[i - K]] = 1
		heappush(Min, P[i])
		heappush(Max, -P[i])
	print(ans)
main()


(n, k) = map(int, input().split())
P = [int(i) for i in input().split()]
import collections
from collections import deque
(M1, M2) = (deque(), deque())
(A1, A2) = ([], [])
M1.append(0)
for i in range(1, n):
	while M1:
		if P[M1[-1]] > P[i]:
			M1.pop()
		else:
			M1.append(i)
			break
	if not M1:
		M1.append(i)
	if M1[0] == i - k - 1:
		M1.popleft()
	if i < k:
		continue
	else:
		A1.append(P[M1[0]])
M2.append(0)
for i in range(1, n):
	while M2:
		if P[M2[-1]] < P[i]:
			M2.pop()
		else:
			M2.append(i)
			break
	if not M2:
		M2.append(i)
	if M2[0] == i - k - 1:
		M2.popleft()
	if i < k:
		continue
	else:
		A2.append(P[M2[0]])
ans = 1
for i in range(n - k):
	if A1[i] == P[i] and A2[i] == P[i + k]:
		continue
	else:
		ans += 1
Q = [0] * n
for i in range(1, n):
	if P[i] > P[i - 1]:
		Q[i] = Q[i - 1] + 1
	else:
		continue
count = 0
for i in range(n):
	if Q[i] == k - 1:
		count += 1
print(ans - max(0, count - 1))


class SegTreeMax:

	def segfunc(self, x, y):
		if x > y:
			return x
		else:
			return y

	def __init__(self, ide, init_val):
		n = len(init_val)
		self.ide_ele = ide
		self.num = 2 ** (n - 1).bit_length()
		self.seg = [self.ide_ele] * 2 * self.num
		for i in range(n):
			self.seg[i + self.num - 1] = init_val[i]
		for i in range(self.num - 2, -1, -1):
			self.seg[i] = self.segfunc(self.seg[2 * i + 1], self.seg[2 * i + 2])

	def update(self, idx, val):
		idx += self.num - 1
		self.seg[idx] = val
		while idx:
			idx = (idx - 1) // 2
			self.seg[idx] = self.segfunc(self.seg[idx * 2 + 1], self.seg[idx * 2 + 2])

	def query(self, begin, end):
		if end <= begin:
			return self.ide_ele
		begin += self.num - 1
		end += self.num - 2
		res = self.ide_ele
		while begin + 1 < end:
			if begin & 1 == 0:
				res = self.segfunc(res, self.seg[begin])
			if end & 1 == 1:
				res = self.segfunc(res, self.seg[end])
				end -= 1
			begin = begin // 2
			end = (end - 1) // 2
		if begin == end:
			res = self.segfunc(res, self.seg[begin])
		else:
			res = self.segfunc(self.segfunc(res, self.seg[begin]), self.seg[end])
		return res

class SegTreeMin:

	def segfunc(self, x, y):
		if x < y:
			return x
		else:
			return y

	def __init__(self, ide, init_val):
		n = len(init_val)
		self.ide_ele = ide
		self.num = 2 ** (n - 1).bit_length()
		self.seg = [self.ide_ele] * 2 * self.num
		for i in range(n):
			self.seg[i + self.num - 1] = init_val[i]
		for i in range(self.num - 2, -1, -1):
			self.seg[i] = self.segfunc(self.seg[2 * i + 1], self.seg[2 * i + 2])

	def update(self, idx, val):
		idx += self.num - 1
		self.seg[idx] = val
		while idx:
			idx = (idx - 1) // 2
			self.seg[idx] = self.segfunc(self.seg[idx * 2 + 1], self.seg[idx * 2 + 2])

	def query(self, begin, end):
		if end <= begin:
			return self.ide_ele
		begin += self.num - 1
		end += self.num - 2
		res = self.ide_ele
		while begin + 1 < end:
			if begin & 1 == 0:
				res = self.segfunc(res, self.seg[begin])
			if end & 1 == 1:
				res = self.segfunc(res, self.seg[end])
				end -= 1
			begin = begin // 2
			end = (end - 1) // 2
		if begin == end:
			res = self.segfunc(res, self.seg[begin])
		else:
			res = self.segfunc(self.segfunc(res, self.seg[begin]), self.seg[end])
		return res

def main():
	(n, k) = map(int, input().split())
	p = list(map(int, input().split()))
	csum = [0] * n
	for i in range(1, n):
		csum[i] += csum[i - 1]
		if p[i - 1] > p[i]:
			csum[i] += 1
	seg_max = SegTreeMax(-float('inf'), p)
	seg_min = SegTreeMin(float('inf'), p)
	ans = 0
	f = True
	for i in range(k - 1, n):
		if csum[i - k + 1] == csum[i]:
			if f:
				ans += 1
				f = False
		elif k <= i and (not (p[i - k] == seg_min.query(i - k, i) and p[i] == seg_max.query(i - k + 1, i + 1))):
			ans += 1
		elif i == k - 1 and csum[i - k + 1] < csum[i]:
			ans += 1
	print(ans)
main()


from heapq import heapify, heappop, heappush
(n, k) = list(map(int, input().split()))
ppp = list(map(int, input().split()))
increases = [int(p1 < p2) for (p1, p2) in zip(ppp, ppp[1:])]
h = k - 1
tmp = sum(increases[:h])
duplicated = [0] * n
first_ascending = True
for (i, q) in enumerate(increases[h:], start=h):
	tmp += q - increases[i - h]
	if tmp == h:
		if first_ascending:
			first_ascending = False
		else:
			duplicated[i + 1] = 1
state = [1] * k + [0] * (n - k)
ans = 1
minq = ppp[:k]
maxq = [-p for p in ppp[:k]]
heapify(minq)
heapify(maxq)
for (i, p) in enumerate(ppp[k:], start=k):
	l = ppp[i - k]
	if l == minq[0] and p > -maxq[0]:
		pass
	elif duplicated[i] == 1:
		pass
	else:
		ans += 1
	state[l] = 2
	state[p] = 1
	while state[minq[0]] == 2:
		heappop(minq)
	while state[-maxq[0]] == 2:
		heappop(maxq)
	heappush(minq, p)
	heappush(maxq, -p)
print(ans)


import sys
readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)

class UnionFind:

	def __init__(self, n):
		self.n = n
		self.parents = [-1] * n

	def find(self, x):
		if self.parents[x] < 0:
			return x
		else:
			self.parents[x] = self.find(self.parents[x])
			return self.parents[x]

	def union(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if x == y:
			return
		if self.parents[x] > self.parents[y]:
			(x, y) = (y, x)
		self.parents[x] += self.parents[y]
		self.parents[y] = x

	def size(self, x):
		return -self.parents[self.find(x)]

	def same(self, x, y):
		return self.find(x) == self.find(y)

	def members(self, x):
		root = self.find(x)
		return [i for i in range(self.n) if self.find(i) == root]

	def roots(self):
		return [i for (i, x) in enumerate(self.parents) if x < 0]

	def group_count(self):
		return len(self.roots())

	def all_group_members(self):
		return {r: self.members(r) for r in self.roots()}

	def __str__(self):
		return '\n'.join(('{}: {}'.format(r, self.members(r)) for r in self.roots()))

def main():
	from collections import deque
	(N, K) = map(int, readline().split())
	P = list(map(int, readline().split()))
	if N == K:
		return print(1)
	p_min = [0] * (N - K)
	p_max = [0] * (N - K)
	p_asc = [0] * (N - K + 1)

	def calc_min():
		que = deque()
		que.append(P[0])
		for i in range(1, K + 1):
			cur = P[i]
			while que and cur < que[-1]:
				que.pop()
			que.append(cur)
		p_min[0] = que[0]
		for i in range(N - K - 1):
			prev = P[i]
			cur = P[i + K + 1]
			if que[0] == prev:
				que.popleft()
			while que and cur < que[-1]:
				que.pop()
			que.append(cur)
			p_min[i + 1] = que[0]

	def calc_max():
		que = deque()
		que.append(P[0])
		for i in range(1, K + 1):
			cur = P[i]
			while que and cur > que[-1]:
				que.pop()
			que.append(cur)
		p_max[0] = que[0]
		for i in range(N - K - 1):
			prev = P[i]
			cur = P[i + K + 1]
			if que[0] == prev:
				que.popleft()
			while que and cur > que[-1]:
				que.pop()
			que.append(cur)
			p_max[i + 1] = que[0]

	def calc_asc():
		prev = -1
		cnt = 0
		for i in range(K):
			cur = P[i]
			if prev < cur:
				cnt += 1
			else:
				cnt = 1
			prev = cur
		p_asc[0] = cnt
		for i in range(N - K):
			cur = P[i + K]
			if prev < cur:
				p_asc[i + 1] = min(p_asc[i] + 1, K)
			else:
				p_asc[i + 1] = 1
			prev = cur
	calc_min()
	calc_max()
	calc_asc()
	uf = UnionFind(N - K + 1)
	asc_list = []
	for i in range(N - K + 1):
		if p_asc[i] == K:
			asc_list.append(i)
	if len(asc_list) > 1:
		for i in range(1, len(asc_list)):
			uf.union(asc_list[0], asc_list[i])
	for i in range(N - K):
		if p_min[i] == P[i] and p_max[i] == P[i + K]:
			uf.union(i, i + 1)
	print(uf.group_count())
main()


(N, K) = map(int, input().split())
P = list(map(int, input().split()))
N0 = 2 ** (N - 1).bit_length()
INF = 10 ** 6
seg_min = [INF] * (2 * N0)
seg_max = [-INF] * (2 * N0)

def update(index, value):
	index += N0 - 1
	seg_min[index] = value
	seg_max[index] = value
	while index > 0:
		index = (index - 1) // 2
		seg_min[index] = min(seg_min[index * 2 + 1], seg_min[index * 2 + 2])
		seg_max[index] = max(seg_max[index * 2 + 1], seg_max[index * 2 + 2])

def query(first, last):
	first += N0 - 1
	last += N0 - 1
	ret_min = INF
	ret_max = -INF
	while first <= last:
		if not first & 1:
			ret_min = min(ret_min, seg_min[first])
			ret_max = max(ret_max, seg_max[first])
		if last & 1:
			ret_min = min(ret_min, seg_min[last])
			ret_max = max(ret_max, seg_max[last])
		first = first // 2
		last = last // 2 - 1
	return (ret_min, ret_max)
for i in range(N):
	update(i, P[i])
ans = 1
for i in range(1, N - K + 1):
	(s, b) = query(i - 1, K + i - 1)
	if s != P[i - 1] or b != P[K + i - 1]:
		ans += 1
kaburi = 0
cnt = 0
for i in range(1, N):
	if P[i - 1] < P[i]:
		cnt += 1
	else:
		cnt = 0
	if cnt == K - 1:
		kaburi += 1
kaburi = max(0, kaburi - 1)
print(ans - kaburi)


from heapq import heappush, heappop
import sys
input = sys.stdin.readline
(N, K) = map(int, input().split())
P = list(map(int, input().split()))
mn = [N] * (N - K)
mx = [-1] * (N - K)
min_heap = []
max_heap = []
for i in range(K):
	heappush(min_heap, P[i])
	heappush(max_heap, -P[i])
used = set()
for i in range(N - K):
	heappush(min_heap, P[i + K])
	heappush(max_heap, -P[i + K])
	while min_heap[0] in used:
		heappop(min_heap)
	while -max_heap[0] in used:
		heappop(max_heap)
	mn[i] = min_heap[0]
	mx[i] = -max_heap[0]
	used.add(P[i])
ans = 1
for i in range(N - K):
	if P[i] != mn[i] or P[i + K] != mx[i]:
		ans += 1
inc = 1
cnt = 0
for i in range(1, N):
	if P[i - 1] < P[i]:
		inc += 1
	else:
		inc = 1
	if inc == K:
		cnt += 1
ans -= max(0, cnt - 1)
print(ans)


def segfunc_min(x, y):
	return min(x, y)

def segfunc_max(x, y):
	return max(x, y)
ide_ele_min = 10 ** 18
ide_ele_max = 0

class segtree:

	def __init__(self, init_val, segfunc, ide_ele):
		n = len(init_val)
		self.segfunc = segfunc
		self.ide_ele = ide_ele
		self.num = 1 << (n - 1).bit_length()
		self.tree = [ide_ele] * 2 * self.num
		for i in range(n):
			self.tree[self.num + i] = init_val[i]
		for i in range(self.num - 1, 0, -1):
			self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

	def update(self, k, x):
		k += self.num
		self.tree[k] = x
		while k > 1:
			self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
			k >>= 1

	def query(self, l, r):
		res = self.ide_ele
		l += self.num
		r += self.num
		while l < r:
			if l & 1:
				res = self.segfunc(res, self.tree[l])
				l += 1
			if r & 1:
				res = self.segfunc(res, self.tree[r - 1])
			l >>= 1
			r >>= 1
		return res
(n, k) = map(int, input().split())
(*p,) = map(int, input().split())
q = [1] * n
ans = n - k + 1
cnt = 1
c = 0
for i in range(n - 1):
	if p[i + 1] > p[i]:
		cnt += 1
	else:
		cnt = 1
	c += cnt >= k
	if cnt > k:
		q[i - k + 1] = 0
if c > 1:
	ans -= c - 1
stn = segtree(p, segfunc_min, ide_ele_min)
stx = segtree(p, segfunc_max, ide_ele_max)
for i in range(n - k):
	if stn.query(i, i + k) == p[i] and stx.query(i + 1, i + k + 1) == p[i + k] and q[i]:
		ans -= 1
print(ans)


(n, k) = map(int, input().split())
p = list(map(int, input().split()))

def init_max(init_val):
	for i in range(n):
		seg[i + num - 1] = init_val[i]
	for i in range(num - 2, -1, -1):
		seg[i] = max(seg[2 * i + 1], seg[2 * i + 2])

def update_max(k, x):
	k += num - 1
	seg[k] = x
	while k + 1:
		k = (k - 1) // 2
		seg[k] = max(seg[k * 2 + 1], seg[k * 2 + 2])

def query_max(p, q):
	if q <= p:
		return ide_ele
	p += num - 1
	q += num - 2
	res = ide_ele
	while q - p > 1:
		if p & 1 == 0:
			res = max(res, seg[p])
		if q & 1 == 1:
			res = max(res, seg[q])
			q -= 1
		p = p // 2
		q = (q - 1) // 2
	if p == q:
		res = max(res, seg[p])
	else:
		res = max(max(res, seg[p]), seg[q])
	return res

def init_min(init_val):
	for i in range(n):
		seg[i + num - 1] = init_val[i]
	for i in range(num - 2, -1, -1):
		seg[i] = min(seg[2 * i + 1], seg[2 * i + 2])

def update_min(k, x):
	k += num - 1
	seg[k] = x
	while k:
		k = (k - 1) // 2
		seg[k] = min(seg[k * 2 + 1], seg[k * 2 + 2])

def query_min(p, q):
	if q <= p:
		return ide_ele
	p += num - 1
	q += num - 2
	res = ide_ele
	while q - p > 1:
		if p & 1 == 0:
			res = min(res, seg[p])
		if q & 1 == 1:
			res = min(res, seg[q])
			q -= 1
		p = p // 2
		q = (q - 1) // 2
	if p == q:
		res = min(res, seg[p])
	else:
		res = min(min(res, seg[p]), seg[q])
	return res
ide_ele = -1
num = 2 ** (n - 1).bit_length()
seg = [ide_ele] * 2 * num
init_max(p)
a = [-1] * (n - k + 1)
for i in range(n - k + 1):
	a[i] = query_max(i, i + k)
ide_ele = n
num = 2 ** (n - 1).bit_length()
seg = [ide_ele] * 2 * num
init_min(p)
b = [-1] * (n - k + 1)
for i in range(n - k + 1):
	b[i] = query_min(i, i + k)
c = [1] * n
d = [True] * n
for i in range(n - 2, -1, -1):
	if p[i] < p[i + 1]:
		c[i] = c[i + 1] + 1
		if c[i] >= k:
			d[i] = False
res = 0
res2 = 0
for i in range(n - k):
	if not d[i]:
		res2 = 1
		continue
	if b[i] == p[i] and a[i + 1] == p[i + k]:
		continue
	res += 1
if d[n - k]:
	res += 1
if n == k:
	print(1)
else:
	print(res + res2)


from collections import deque

def slidemax(X, k):
	q = deque([])
	ret = []
	for i in range(len(X)):
		while q and q[-1][1] <= X[i]:
			q.pop()
		deque.append(q, (i + k, X[i]))
		if q[0][0] == i:
			deque.popleft(q)
		if i >= k - 1:
			ret.append(q[0][1])
	return ret

def slidemin(X, k):
	q = deque([])
	ret = []
	for i in range(len(X)):
		while q and q[-1][1] >= X[i]:
			q.pop()
		deque.append(q, (i + k, X[i]))
		if q[0][0] == i:
			deque.popleft(q)
		if i >= k - 1:
			ret.append(q[0][1])
	return ret
(N, K) = map(int, input().split())
A = [int(a) for a in input().split()]
a = 0
l = -1
cnt = 0
for i in range(1, N):
	if A[i - 1] > A[i]:
		a = i
	if i >= K - 1 and a <= i - K + 1:
		if i - l > 1:
			cnt += 1
		l = i
MA = slidemax(A, K)
MI = slidemin(A, K)
ans = 1 - max(cnt - 1, 0)
l = -1
for i in range(K, N):
	if MI[i - K] != A[i - K] or MA[i - K + 1] != A[i]:
		ans += 1
print(ans)


from collections import deque
(n, k) = map(int, input().split())
p = list(map(int, input().split()))
c = 0
l = [1] * (n - k + 1)
for i in range(k - 1):
	if p[i] > p[i + 1]:
		c += 1
if c == 0:
	l[0] = 0
for i in range(k - 1, n - 1):
	if p[i] > p[i + 1]:
		c += 1
	if p[i - k + 1] > p[i - k + 2]:
		c -= 1
	if c == 0:
		l[i - k + 2] = 0
k -= 1
qa = deque([])
a = [0] * (n - k + 1)
qb = deque([])
b = [0] * (n - k + 1)
for i in range(n):
	while qa and p[qa[-1]] > p[i]:
		qa.pop()
	while qb and p[qb[-1]] < p[i]:
		qb.pop()
	qa.append(i)
	qb.append(i)
	if qa[0] == i - k:
		qa.popleft()
	if qb[0] == i - k:
		qb.popleft()
	if i >= k - 1:
		a[i - k + 1] = p[qa[0]]
		b[i - k + 1] = p[qb[0]]
ans = l[0]
for i in range(n - k - 1):
	if (p[i] > a[i + 1] or b[i + 1] > p[i + k + 1]) and l[i + 1]:
		ans += 1
print(ans + 1 - min(l))


def main():
	import sys
	input = sys.stdin.readline
	(n, k) = map(int, input().split())
	x = list(map(int, input().split()))
	min_list = []
	max_list = []
	m = 262143 + n
	segtree = [-1] * m
	for i in range(262143, m):
		segtree[i] = x[i - 262143]
	for i in range(262142, -1, -1):
		j = 2 * i + 1
		if j >= m:
			segtree[i] = -1
		elif j + 1 >= m:
			segtree[i] = segtree[j]
		else:
			segtree[i] = min(segtree[j], segtree[j + 1])
	for i in range(n - k + 2):
		qq = [(i, i + k - 2, 0, 1)]
		s = set()
		while qq:
			(ii, jj, now, kubun) = qq.pop()
			now2 = now - kubun + 1
			width = 262144 // kubun
			left = width * now2
			right = width * (now2 + 1) - 1
			if ii <= left and right <= jj:
				s.add(segtree[now])
			elif jj < left or right < ii:
				continue
			else:
				qq.append((ii, jj, 2 * now + 1, 2 * kubun))
				qq.append((ii, jj, 2 * now + 2, 2 * kubun))
		min_list.append(min(s))
	for i in range(262142, -1, -1):
		j = 2 * i + 1
		if j >= m:
			segtree[i] = n + 1
		elif j + 1 >= m:
			segtree[i] = segtree[j]
		else:
			segtree[i] = max(segtree[j], segtree[j + 1])
	for i in range(n - k + 2):
		qq = [(i, i + k - 2, 0, 1)]
		s = set()
		while qq:
			(ii, jj, now, kubun) = qq.pop()
			now2 = now - kubun + 1
			width = 262144 // kubun
			left = width * now2
			right = width * (now2 + 1) - 1
			if ii <= left and right <= jj:
				s.add(segtree[now])
			elif jj < left or right < ii:
				continue
			else:
				qq.append((ii, jj, 2 * now + 1, 2 * kubun))
				qq.append((ii, jj, 2 * now + 2, 2 * kubun))
		max_list.append(max(s))
	cnt = 0
	flag = [True] * (n - k + 1)
	first = False
	for i in range(n - 1):
		if x[i] < x[i + 1]:
			cnt += 1
		else:
			cnt = 0
		if cnt >= k - 1:
			if first == False:
				first = True
			else:
				flag[i - k + 2] = False
	for i in range(1, n - k + 1):
		if x[i - 1] < min_list[i] and max_list[i] < x[i + k - 1]:
			flag[i] = False
	print(sum(flag))
main()


(N, K) = map(int, input().split())
P = list(map(int, input().split()))
INF = float('inf')
num = 2 ** (N - 1).bit_length()
segmin = [INF] * num * 2
segmax = [-INF] * num * 2
for i in range(N):
	segmin[num + i - 1] = P[i]
	segmax[num + i - 1] = P[i]
for i in range(num - 2, -1, -1):
	segmin[i] = min(segmin[2 * i + 1], segmin[2 * i + 2])
	segmax[i] = max(segmax[2 * i + 1], segmax[2 * i + 2])

def query(seg, f, boundary, p, q):
	p += num - 1
	q += num - 2
	res = boundary
	while q - p > 1:
		if p & 1 == 0:
			res = f(res, seg[p])
		if q & 1 == 1:
			res = f(res, seg[q])
			q -= 1
		p = p // 2
		q = (q - 1) // 2
	if p == q:
		res = f(res, seg[p])
	else:
		res = f(f(res, seg[p]), seg[q])
	return res
ans = 1
for i in range(N - K):
	if not (P[i] < query(segmin, min, INF, i + 1, i + K) and P[i + K] > query(segmax, max, -INF, i + 1, i + K)):
		ans += 1
combo = 0
nord = 0
for i in range(1, N):
	if P[i] > P[i - 1]:
		combo += 1
	else:
		combo = 0
	if combo == K - 1:
		nord += 1
print(ans - max(0, nord - 1))


import heapq
from collections import deque, Counter
(N, K) = map(int, input().split())
P = list(map(int, input().split()))
q = deque()
q_idx = []
L = []
for (i, p) in enumerate(P):
	while q and p <= q[-1][1]:
		(idx, _) = q.pop()
		heapq.heappush(q_idx, idx)
	q.append((i, p))
	L.append(q_idx[0] if q_idx else -1)
	if q and q[0][0] <= i + 1 - K:
		(idx, _) = q.popleft()
	if q_idx and q_idx[0] <= i + 1 - K:
		heapq.heappop(q_idx)
L = L[K - 1:]
P = [-p for p in P]
P.reverse()
q = deque()
q_idx = []
R = []
for (i, p) in enumerate(P):
	while q and p <= q[-1][1]:
		(idx, _) = q.pop()
		heapq.heappush(q_idx, idx)
	q.append((i, p))
	R.append(N - 1 - q_idx[0] if q_idx else -1)
	if q and q[0][0] <= i + 1 - K:
		(idx, _) = q.popleft()
	if q_idx and q_idx[0] <= i + 1 - K:
		heapq.heappop(q_idx)
R = R[K - 1:]
R.reverse()
print(len(Counter(zip(L, R))))


from collections import deque
from bisect import bisect_right
(N, K) = map(int, input().split())
P = list(map(int, input().split()))
Lmax = []
Lmin = []
if P[1] > P[0]:
	flag = 1
else:
	flag = -1
for i in range(2, N):
	if P[i] > P[i - 1]:
		if flag == 1:
			continue
		else:
			Lmin.append([i - 1, P[i - 1]])
			flag = 1
	elif flag == 1:
		Lmax.append([i - 1, P[i - 1]])
		flag = -1
	else:
		continue
cnt = 0
flagMono = 0
indmin = bisect_right(Lmin, [K - 1, P[K - 1]])
Smax = deque([0])
Smin = deque([0])
for i in range(1, K):
	while Smax:
		if P[Smax[-1]] < P[i]:
			Smax.pop()
		else:
			break
	Smax.append(i)
	while Smin:
		if P[Smin[-1]] > P[i]:
			Smin.pop()
		else:
			break
	Smin.append(i)
if P[0] == P[Smin[0]] and P[K - 1] == P[Smax[0]] and (len(Lmin) == 0 or indmin == 0 or Lmin[indmin - 1][0] == 0):
	flagMono = 1
	cnt += 1
elif P[0] == P[Smin[0]] and K < N and (P[K] > P[Smax[0]]):
	pass
else:
	cnt += 1
for i in range(1, N - K + 1):
	if Smax[0] == i - 1:
		Smax.popleft()
	while Smax:
		if P[Smax[-1]] < P[i + K - 1]:
			Smax.pop()
		else:
			break
	Smax.append(i + K - 1)
	if Smin[0] == i - 1:
		Smin.popleft()
	while Smin:
		if P[Smin[-1]] > P[i + K - 1]:
			Smin.pop()
		else:
			break
	Smin.append(i + K - 1)
	indmin = bisect_right(Lmin, [i + K - 1, P[i + K - 1]])
	if P[i] == P[Smin[0]] and P[i + K - 1] == P[Smax[0]] and (len(Lmin) == 0 or indmin == 0 or Lmin[indmin - 1][0] <= i):
		if flagMono == 0:
			flagMono = 1
			cnt += 1
		else:
			pass
	elif P[i] == P[Smin[0]] and i + K < N and (P[i + K] > P[Smax[0]]):
		continue
	else:
		cnt += 1
print(cnt)


(n, k) = map(int, input().split())
p = list(map(int, input().split()))
if n == k:
	print(1)
	exit()

def slide_min(n, k, p):
	res = [0] * n
	deq = [0] * n
	s = 0
	t = 0
	for i in range(n):
		while s < t:
			if p[deq[t - 1]] >= p[i]:
				t -= 1
			else:
				break
		deq[t] = i
		t += 1
		if i - k + 1 >= 0:
			res[i - k + 1] = p[deq[s]]
			if deq[s] == i - k + 1:
				s += 1
	return res

def slide_max(n, k, p):
	res = [0] * n
	deq = [0] * n
	s = 0
	t = 0
	for i in range(n):
		while s < t:
			if p[deq[t - 1]] < p[i]:
				t -= 1
			else:
				break
		deq[t] = i
		t += 1
		if i - k + 1 >= 0:
			res[i - k + 1] = p[deq[s]]
			if deq[s] == i - k + 1:
				s += 1
	return res
s_min = slide_min(n, k, p)
s_max = slide_max(n, k, p)
ans = 1
for i in range(n - k):
	if p[i] > s_min[i] or p[i + k] != s_max[i + 1]:
		ans += 1
mode = 0
count = 0
e = 0
for i in range(n - 1):
	if p[i] < p[i + 1]:
		if mode == 0:
			count = 2
			mode = 1
		else:
			count += 1
	else:
		mode = 0
		if count >= k:
			e += 1
			count = 0
if mode == 1 and count >= k:
	e += 1
if e > 1:
	ans -= e - 1
print(ans)


(N, K) = map(int, input().split())
P = list(map(int, input().split()))
N0 = 2 ** (N - 1).bit_length()
INF = 2 ** 31 - 1
data_m = [INF] * (2 * N0)
data_M = [INF] * (2 * N0)

def update(k, x, data):
	k += N0 - 1
	data[k] = x
	while k >= 0:
		k = (k - 1) // 2
		data[k] = min(data[2 * k + 1], data[2 * k + 2])

def query(l, r, data):
	L = l + N0
	R = r + N0
	s = INF
	while L < R:
		if R & 1:
			R -= 1
			s = min(s, data[R - 1])
		if L & 1:
			s = min(s, data[L - 1])
			L += 1
		L >>= 1
		R >>= 1
	return s
for i in range(N):
	update(i, P[i], data_m)
	update(i, -P[i], data_M)
s = [1] * N
r = 0
for l in range(N):
	r = max(l, r)
	while r < N - 1:
		if P[r] < P[r + 1]:
			r += 1
		else:
			break
	s[l] = r - l + 1
ans = 0
if s[0] < K:
	ans += 1
for i in range(1, N - K + 1):
	if query(i - 1, i + K, data_m) != P[i - 1] or query(i - 1, i + K, data_M) != -P[i + K - 1]:
		if s[i] < K:
			ans += 1
if max(s) >= K:
	ans += 1
print(ans)


(N, K) = map(int, input().split())
P = list(map(int, input().split()))
if K == N:
	print(1)
	exit()
cum_asc = [0]
for (p, q) in zip(P, P[1:]):
	cum_asc.append(cum_asc[-1] + int(p < q))
all_asc = []
for i in range(N - K + 1):
	all_asc.append(cum_asc[i + K - 1] - cum_asc[i] == K - 1)
from collections import deque
sldmin = []
sldmax = []
qmin = deque()
qmax = deque()
for (i, p) in enumerate(P):
	while qmin and qmin[-1] > p:
		qmin.pop()
	qmin.append(p)
	if i - K - 1 >= 0 and P[i - K - 1] == qmin[0]:
		qmin.popleft()
	while qmax and qmax[-1] < p:
		qmax.pop()
	qmax.append(p)
	if i - K - 1 >= 0 and P[i - K - 1] == qmax[0]:
		qmax.popleft()
	if i >= K:
		sldmin.append(qmin[0])
		sldmax.append(qmax[0])

class UnionFind:

	def __init__(self, N):
		self.parent = [i for i in range(N)]
		self.rank = [0] * N
		self.count = 0

	def root(self, a):
		if self.parent[a] == a:
			return a
		else:
			self.parent[a] = self.root(self.parent[a])
			return self.parent[a]

	def is_same(self, a, b):
		return self.root(a) == self.root(b)

	def unite(self, a, b):
		ra = self.root(a)
		rb = self.root(b)
		if ra == rb:
			return
		if self.rank[ra] < self.rank[rb]:
			self.parent[ra] = rb
		else:
			self.parent[rb] = ra
			if self.rank[ra] == self.rank[rb]:
				self.rank[ra] += 1
		self.count += 1

	def components(self):
		return len(self.parent) - self.count
uf = UnionFind(N - K + 2)
for (i, (l, r, mn, mx)) in enumerate(zip(P, P[K:], sldmin, sldmax)):
	if l == mn and r == mx:
		uf.unite(i, i + 1)
if all((f == False for f in all_asc)):
	print(uf.components() - 1)
	exit()
def_i = N - K + 1
for (i, f) in enumerate(all_asc):
	if f:
		uf.unite(i, def_i)
print(uf.components())


from collections import Counter
from heapq import heappush, heappop
(N, K, *P) = map(int, open(0).read().split())
i = 0
ans = 1
Cnt = Counter(P[:K])
mls = []
Mls = []
for i in range(K):
	heappush(mls, P[i])
	heappush(Mls, -P[i])
for i in range(N - K):
	Cnt[P[i]] -= 1
	Cnt[P[i + K]] += 1
	if not (P[i] == mls[0] and P[i + K] >= -Mls[0]):
		ans += 1
	heappush(mls, P[i + K])
	heappush(Mls, -P[i + K])
	while Cnt[mls[0]] == 0:
		heappop(mls)
	while Cnt[-Mls[0]] == 0:
		heappop(Mls)
i = 0
flag = False
for j in range(1, N):
	if P[j] < P[j - 1]:
		if j - i >= K:
			ans -= 1
			flag = True
		i = j
if j - i >= K - 1:
	flag = True
	ans -= 1
if flag:
	ans += 1
print(ans)


import sys
from collections import deque
from bisect import bisect_left
input = sys.stdin.buffer.readline
(N, K) = map(int, input().split())
Ps = list(map(int, input().split()))
downs = []
for i in range(N - 1):
	if Ps[i + 1] < Ps[i]:
		downs.append(i)
if not downs:
	print(1)
	exit()
min_wait = deque()
max_wait = deque()
for i in range(K):
	while min_wait and min_wait[-1] > Ps[i]:
		min_wait.pop()
	min_wait.append(Ps[i])
	while max_wait and max_wait[-1] < Ps[i]:
		max_wait.pop()
	max_wait.append(Ps[i])
change_nothing = downs[0] >= K - 1
if change_nothing:
	ans = 0
else:
	ans = 1
for i in range(K, N):
	while min_wait and min_wait[-1] > Ps[i]:
		min_wait.pop()
	min_wait.append(Ps[i])
	while max_wait and max_wait[-1] < Ps[i]:
		max_wait.pop()
	max_wait.append(Ps[i])
	if min_wait[0] != Ps[i - K] or max_wait[0] != Ps[i]:
		t = bisect_left(downs, i - K + 1)
		if t < len(downs):
			if downs[t] >= i:
				change_nothing = True
			else:
				ans += 1
		else:
			if downs[-1] + K < N:
				change_nothing = True
			break
	if min_wait[0] == Ps[i - K]:
		min_wait.popleft()
	if max_wait[0] == Ps[i - K]:
		max_wait.popleft()
if change_nothing:
	ans += 1
print(ans)


class segtree:

	def segfunc(x, y):
		return min(x, y)
	ide_ele = -1
	n = 1
	init_val = [0] * n
	num = 2 ** (n - 1).bit_length()
	seg = [ide_ele] * 2 * num

	def __init__(self, INIT_VAL, SEGFUNC, IDE_ELE):
		self.ide_ele = IDE_ELE
		self.init_val = [i for i in INIT_VAL]
		self.segfunc = SEGFUNC
		self.n = len(self.init_val)
		self.num = 2 ** (self.n - 1).bit_length()
		self.seg = [self.ide_ele] * 2 * self.num
		for i in range(self.n):
			self.seg[i + self.num - 1] = self.init_val[i]
		for i in range(self.num - 2, -1, -1):
			self.seg[i] = self.segfunc(self.seg[2 * i + 1], self.seg[2 * i + 2])

	def update(self, k, x):
		k += self.num - 1
		self.seg[k] = x
		while k + 1:
			k = (k - 1) // 2
			self.seg[k] = self.segfunc(self.seg[k * 2 + 1], self.seg[k * 2 + 2])

	def query(self, p, q):
		if q <= p:
			return self.ide_ele
		p += self.num - 1
		q += self.num - 2
		res = self.ide_ele
		while q - p > 1:
			if p & 1 == 0:
				res = self.segfunc(res, self.seg[p])
			if q & 1 == 1:
				res = self.segfunc(res, self.seg[q])
				q -= 1
			p = p // 2
			q = (q - 1) // 2
		if p == q:
			res = self.segfunc(res, self.seg[p])
		else:
			res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
		return res

class UnionFind:
	n = 1
	par = [0]
	rnk = [0]

	def __init__(self, size):
		self.n = size
		self.par = [i for i in range(self.n)]
		self.rnk = [0 for i in range(self.n)]

	def find(self, vertex1):
		if self.par[vertex1] == vertex1:
			return vertex1
		else:
			self.par[vertex1] = self.find(self.par[vertex1])
			return self.par[vertex1]

	def unite(self, vertex1, vertex2):
		vertex1 = self.find(vertex1)
		vertex2 = self.find(vertex2)
		if vertex1 == vertex2:
			return
		if self.rnk[vertex1] < self.rnk[vertex2]:
			self.par[vertex1] = vertex2
		else:
			self.par[vertex2] = vertex1
			if self.rnk[vertex1] == self.rnk[vertex2]:
				self.rnk[vertex1] += 1

	def same(self, vetrex1, vertex2):
		return self.find(vetrex1) == self.find(vertex2)
(N, K) = map(int, input().split())
P = [int(i) for i in input().split()]
mintree = segtree(P, min, N)
maxtree = segtree(P, max, -1)
G = UnionFind(N - K + 1)
for i in range(N - K):
	m = mintree.query(i + 1, i + K)
	M = maxtree.query(i + 1, i + K)
	if P[i] < m and M < P[i + K]:
		G.unite(i, i + 1)
aaa = [G.find(i) for i in range(N - K + 1)]
Q = [1 for i in range(N)]
for i in range(N - 1):
	if P[i] < P[i + 1]:
		Q[i + 1] = Q[i] + 1
	else:
		Q[i + 1] = 1
tmp = 0
for i in range(N):
	if Q[i] == K:
		tmp += 1
if tmp > 0:
	tmp -= 1
print(len(set(aaa)) - tmp)


from operator import lt, gt

def hoge(a, K, op):
	from collections import deque
	dq = deque()
	(pop, popleft, append) = (dq.pop, dq.popleft, dq.append)
	for (i, v) in zip(range(K), a):
		while dq and (not op(a[dq[-1]], v)):
			pop()
		append(i)
	yield a[dq[0]]
	for i in range(K, len(a)):
		while dq and (not op(a[dq[-1]], a[i])):
			pop()
		append(i)
		if dq[0] == i - K:
			popleft()
		yield a[dq[0]]
(N, K) = map(int, input().split())
a = tuple(map(int, input().split()))
inv_flag = [0] * N
for (i, (x, y)) in enumerate(zip(a, a[1:]), start=1):
	inv_flag[i] = i if x > y else inv_flag[i - 1]
min_coro = hoge(a, K, lt)
max_coro = hoge(a, K, gt)
(prev_min, prev_max) = (next(min_coro), next(max_coro))
(ans, flag) = (inv_flag[K - 1] != 0, inv_flag[K - 1] == 0)
for (l, r, x, y) in zip(range(1, N), range(K, N), min_coro, max_coro):
	if inv_flag[l] == inv_flag[r]:
		flag = 1
	elif not (prev_min < x and prev_max < y):
		ans += 1
	(prev_min, prev_max) = (x, y)
print(ans + flag)


import sys
sys.setrecursionlimit(10 ** 8)
input = sys.stdin.readline
(N, K) = map(int, input().split())
P = list(map(int, input().split()))

class SegTree:

	def __init__(self, n, init_list, segfunc, ide_ele):
		self.num = 2 ** (n - 1).bit_length()
		self.seg = [ide_ele] * (2 * self.num)
		self.segfunc = segfunc
		self.ide_ele = ide_ele
		for i in range(n):
			self.seg[i + self.num - 1] = init_list[i]
		for i in range(self.num - 2, -1, -1):
			self.seg[i] = segfunc(self.seg[2 * i + 1], self.seg[2 * i + 2])

	def update(self, k, x):
		k += self.num - 1
		self.seg[k] = x
		while k:
			k = (k - 1) // 2
			self.seg[k] = self.segfunc(self.seg[2 * k + 1], self.seg[2 * k + 2])

	def query(self, l, r):
		if r <= l:
			return self.ide_ele
		l += self.num - 1
		r += self.num - 2
		ret = self.ide_ele
		while r - l > 1:
			if l & 1 == 0:
				ret = self.segfunc(ret, self.seg[l])
			if r & 1 == 1:
				ret = self.segfunc(ret, self.seg[r])
				r -= 1
			l = l // 2
			r = (r - 1) // 2
		if r == l:
			ret = self.segfunc(ret, self.seg[r])
		else:
			ret = self.segfunc(ret, self.seg[l])
			ret = self.segfunc(ret, self.seg[r])
		return ret

def segfunc(x, y):
	return min(x, y)

def segfunc2(x, y):
	return max(x, y)
INF = 10 ** 9
segtree = SegTree(N, P, segfunc, INF)
segtree_max = SegTree(N, P, segfunc2, 0)
from queue import Queue
zouka = [1]
num = 1
for i in range(N - 1):
	if P[i + 1] > P[i]:
		num += 1
	else:
		num = 1
	zouka.append(num)
mini = INF
maxi = 0
q = Queue()
for p in P[:K]:
	mini = min(mini, p)
	maxi = max(maxi, p)
	q.put(p)
ans = 1
m = 0
if zouka[K - 1] - zouka[0] == K - 1:
	m += 1
	ans = 0
for i in range(1, N - K + 1):
	remove = q.get()
	q.put(P[i + K - 1])
	if zouka[i + K - 1] - zouka[i] == K - 1:
		m += 1
	elif P[i + K - 1] > maxi and remove == mini:
		None
	else:
		ans += 1
	maxi = segtree_max.query(i, i + K)
	mini = segtree.query(i, i + K)
if m >= 1:
	ans += 1
print(max(1, ans))


(n, k) = map(int, input().split())
p = list(map(int, input().split()))
from collections import deque

def slide_max_index(a, K):
	N = len(a)
	max_idx = [0] * N
	deq = deque()
	for i in range(0, N):
		while len(deq) > 0 and deq[0] <= i - K:
			deq.popleft()
		while len(deq) > 0 and a[deq[-1]] < a[i]:
			deq.pop()
		deq.append(i)
		max_idx[i] = deq[0]
	return max_idx

def slide_min_index(a, K):
	N = len(a)
	min_idx = [0] * N
	deq = deque()
	for i in range(0, N):
		while len(deq) > 0 and deq[0] <= i - K:
			deq.popleft()
		while len(deq) > 0 and a[deq[-1]] > a[i]:
			deq.pop()
		deq.append(i)
		min_idx[i] = deq[0]
	return min_idx
min_idx = slide_min_index(p, k + 1)
max_idx = slide_max_index(p, k + 1)
eq = list(range(n - k + 1))
for i in range(n - (k + 1) + 1):
	if i == min_idx[i + k] and i + k == max_idx[i + k]:
		eq[i + 1] = eq[i]
pre = p[0]
a = [0]
c = 0
for pi in p[1:]:
	if pre < pi:
		c += 1
	else:
		c = 0
	pre = pi
	a.append(c)
eqi = -1
for i in range(n - k + 1):
	if a[i + k - 1] >= k - 1:
		if eqi == -1:
			eqi = i
		else:
			eq[i] = eqi
print(len(set(eq)))


from sys import stdin
from collections import deque
(N, K) = [int(x) for x in stdin.readline().rstrip().split()]
P = [int(x) for x in stdin.readline().rstrip().split()]
ans = N - K + 1
D = deque([x for x in P[:K]])
oc = 0
ordered_twice = False
for i in range(len(D) - 1):
	if D[i] <= D[i + 1]:
		oc += 1
Q = deque([])
Q_min = []
Q_max = []
for i in range(N):
	while len(Q) > 0 and P[Q[len(Q) - 1]] >= P[i]:
		Q.pop()
	Q.append(i)
	if Q[len(Q) - 1] >= K - 1:
		Q_min.append(P[Q[0]])
		if Q[0] == i + 1 - K:
			Q.popleft()
PP = [-x for x in P]
Q = deque([])
for i in range(N):
	while len(Q) > 0 and PP[Q[len(Q) - 1]] >= PP[i]:
		Q.pop()
	Q.append(i)
	if Q[len(Q) - 1] >= K - 1:
		Q_max.append(-PP[Q[0]])
		if Q[0] == i + 1 - K:
			Q.popleft()
for i in range(N - K + 1):
	if i > 0:
		D.popleft()
		D.append(P[i + K - 1])
		if P[i - 1] <= D[0]:
			oc -= 1
		if D[K - 2] <= D[K - 1]:
			oc += 1
		if Q_min[i - 1] == P[i - 1] and Q_max[i] == D[-1] or (oc == K - 1 and ordered_twice):
			ans -= 1
	if oc == K - 1:
		ordered_twice = True
print(ans)


NN = 18
MA = [-1] * ((1 << NN + 1) - 1)
MI = [1 << 100] * ((1 << NN + 1) - 1)

def update(a, x):
	i = (1 << NN) - 1 + a
	MI[i] = x
	MA[i] = x
	while True:
		i = (i - 1) // 2
		MI[i] = min(MI[2 * i + 1], MI[2 * i + 2])
		MA[i] = max(MA[2 * i + 1], MA[2 * i + 2])
		if i == 0:
			break

def rangemin(a, b):
	l = a + (1 << NN)
	r = b + (1 << NN)
	mi = 1 << 100
	while l < r:
		if l % 2:
			mi = min(mi, MI[l - 1])
			l += 1
		if r % 2:
			r -= 1
			mi = min(mi, MI[r - 1])
		l >>= 1
		r >>= 1
	return mi

def rangemax(a, b):
	l = a + (1 << NN)
	r = b + (1 << NN)
	ma = -1
	while l < r:
		if l % 2:
			ma = max(ma, MA[l - 1])
			l += 1
		if r % 2:
			r -= 1
			ma = max(ma, MA[r - 1])
		l >>= 1
		r >>= 1
	return ma
(N, K) = map(int, input().split())
A = [int(a) for a in input().split()]
a = 0
l = -1
cnt = 0
for i in range(1, N):
	if A[i - 1] > A[i]:
		a = i
	if i >= K - 1 and a <= i - K + 1:
		if i - l > 1:
			cnt += 1
		l = i
ans = 1 - max(cnt - 1, 0)
for i in range(N):
	update(i, A[i])
	if i >= K:
		mi = rangemin(i - K, i)
		ma = rangemax(i - K + 1, i + 1)
		if mi != A[i - K] or ma != A[i]:
			ans += 1
print(ans)


class SegTree:

	def __init__(self, seq, fx, ex):
		self.n = len(seq)
		self.fx = fx
		self.ex = ex
		self.size = 1 << (self.n - 1).bit_length()
		self.tree = [ex] * (self.size * 2)
		for (i, x) in enumerate(seq, start=self.size):
			self.tree[i] = x
		for i in reversed(range(1, self.size)):
			self.tree[i] = self.fx(self.tree[2 * i], self.tree[2 * i + 1])

	def update(self, i, x):
		i += self.size
		self.tree[i] = x
		while i > 1:
			i >>= 1
			self.tree[i] = self.fx(self.tree[2 * i], self.tree[2 * i + 1])

	def query(self, l, r):
		tmp_l = self.ex
		tmp_r = self.ex
		l += self.size
		r += self.size
		while l < r:
			if l & 1:
				tmp_l = self.fx(tmp_l, self.tree[l])
				l += 1
			if r & 1:
				tmp_r = self.fx(self.tree[r - 1], tmp_r)
			l >>= 1
			r >>= 1
		return self.fx(tmp_l, tmp_r)
(n, k) = (int(x) for x in input().split())
P = list((int(x) for x in input().split()))
min_seg = SegTree(P, fx=min, ex=10 ** 18)
max_seg = SegTree(P, fx=max, ex=0)
asc_count = [1] * n
for i in range(1, n):
	if P[i] > P[i - 1]:
		asc_count[i] = asc_count[i - 1] + 1
ans = 1
no_count = 0
if asc_count[k - 1] >= k:
	no_count += 1
for i in range(1, n - k + 1):
	if P[i - 1] != min_seg.query(i - 1, i + k - 1) or P[i + k - 1] != max_seg.query(i, i + k):
		ans += 1
		if asc_count[i + k - 1] >= k:
			no_count += 1
print(ans - max(no_count - 1, 0))


class BITbisect:

	def __init__(self, max):
		self.max = max
		self.data = [0] * (self.max + 1)

	def query_sum(self, i):
		s = 0
		while i > 0:
			s += self.data[i]
			i -= i & -i
		return s

	def add(self, i, x):
		while i <= self.max:
			self.data[i] += x
			i += i & -i

	def insert(self, x):
		self.add(x, 1)

	def delete(self, x):
		self.add(x, -1)

	def count(self, x):
		return self.query_sum(x) - self.query_sum(x - 1)

	def length(self):
		return self.query_sum(self.max)

	def search(self, c):
		c += 1
		s = 0
		ind = 0
		l = self.max.bit_length()
		for i in reversed(range(l)):
			if ind + (1 << i) <= self.max:
				if s + self.data[ind + (1 << i)] < c:
					s += self.data[ind + (1 << i)]
					ind += 1 << i
		if ind == self.max:
			return False
		return ind + 1

	def bisect_right(self, x):
		return self.query_sum(x)

	def bisect_left(self, x):
		if x == 1:
			return 0
		return self.query_sum(x - 1)

	def display(self):
		print('inside BIT:', end=' ')
		for x in range(1, self.max + 1):
			if self.count(x):
				c = self.count(x)
				for _ in range(c):
					print(x, end=' ')
		print()
import sys
input = sys.stdin.readline
(N, K) = map(int, input().split())
A = list(map(int, input().split()))
bit = BITbisect(N)
for i in range(K):
	bit.insert(A[i] + 1)
ans = 1
for i in range(K, N):
	if A[i - K] + 1 != bit.search(0) or A[i] + 1 <= bit.search(K - 1):
		ans += 1
	bit.delete(A[i - K] + 1)
	bit.insert(A[i] + 1)
c = 1
p = 0
for i in range(N - 1):
	if A[i] < A[i + 1]:
		c += 1
	else:
		if c >= K:
			p += 1
		c = 1
if c >= K:
	p += 1
ans -= max(p - 1, 0)
print(ans)


(n, k) = map(int, input().split())
p = list(map(int, input().split()))
from heapq import heappop, heappush, heapify
import heapq

class pqheap:

	def __init__(self, key=None):
		self.p = list()
		self.q = list()

	def insert(self, x):
		heapq.heappush(self.p, x)
		return

	def erase(self, x):
		heapq.heappush(self.q, x)
		return

	def minimum(self):
		while self.q and self.p[0] == self.q[0]:
			heapq.heappop(self.p)
			heapq.heappop(self.q)
		return self.p[0] if len(self.p) > 0 else None
minheap = pqheap()
maxheap = pqheap()
for i in range(k):
	minheap.insert(p[i])
	maxheap.insert(-p[i])
ans = 1
premin = minheap.minimum()
premax = -maxheap.minimum()
for i in range(k, n):
	ins = p[i]
	era = p[i - k]
	minheap.erase(era)
	maxheap.erase(-era)
	minheap.insert(ins)
	maxheap.insert(-ins)
	if premin == era and ins == -maxheap.minimum():
		pass
	else:
		ans += 1
	premax = -maxheap.minimum()
	premin = minheap.minimum()
ans0 = 0
now = 1
pre = p[0]
for x in p[1:]:
	if x > pre:
		now += 1
	else:
		now = 1
	if now == k:
		ans0 += 1
	pre = x
print(ans - max(0, ans0 - 1))


import math, string, itertools, fractions, heapq, collections, re, array, bisect, sys, copy, functools
import time, random
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20
eps = 1.0 / 10 ** 10
mod = 10 ** 9 + 7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]

def LI():
	return list(map(int, sys.stdin.readline().split()))

def LLI():
	return [list(map(int, l.split())) for l in sys.stdin.readlines()]

def LI_():
	return [int(x) - 1 for x in sys.stdin.readline().split()]

def LF():
	return [float(x) for x in sys.stdin.readline().split()]

def LS():
	return sys.stdin.readline().split()

def I():
	return int(sys.stdin.readline())

def F():
	return float(sys.stdin.readline())

def S():
	return input()

def pf(s):
	return print(s, flush=True)

def pe(s):
	return print(str(s), file=sys.stderr)

def JA(a, sep):
	return sep.join(map(str, a))

def JAA(a, s, t):
	return s.join((t.join(map(str, b)) for b in a))

def ff(n, k, p):
	s = set()
	for i in range(n - k + 1):
		t = tuple(p[:i] + sorted(p[i:i + k]) + p[i + k:])
		s.add(t)
	return len(s)

def main():
	(n, k) = LI()
	p = LI()
	qc = [None] * n
	for i in range(n - 1):
		if p[i] > p[i + 1]:
			qc[i + 1] = True
	ec = -1
	iq = []
	aq = []
	for i in range(k):
		if qc[i]:
			ec = i
		heapq.heappush(iq, p[i])
		heapq.heappush(aq, -p[i])
	r = 0
	if ec > 0:
		r += 1
	s = set()
	for i in range(k, n):
		if qc[i]:
			ec = i
		t = p[i]
		u = p[i - k]
		heapq.heappush(iq, t)
		while iq[0] in s:
			heapq.heappop(iq)
		while -aq[0] in s:
			heapq.heappop(aq)
		heapq.heappush(aq, -t)
		if iq[0] != u or aq[0] != -t:
			if ec > i - k + 1:
				r += 1
		s.add(u)
	rr = 0
	c = 1
	for i in range(1, n):
		if p[i] > p[i - 1]:
			c += 1
			if c >= k:
				rr = 1
				break
		else:
			c = 1
	return r + rr
print(main())


import sys
from operator import itemgetter
from fractions import gcd
from math import ceil, floor, sqrt
from copy import deepcopy
from collections import Counter, deque
import heapq
import random
from functools import reduce
sys.setrecursionlimit(200000)
input = sys.stdin.readline

def ii():
	return int(input())

def mi():
	return map(int, input().rstrip().split())

def lmi():
	return list(map(int, input().rstrip().split()))

def fi():
	return float(input())

def mfi():
	return map(float, input().rstrip().split())

def lmfi():
	return list(map(float, input().rstrip().split()))

def li():
	return list(input().rstrip())

def debug(*args, sep=' ', end='\n'):
	print('debug:', *args, file=sys.stderr, sep=sep, end=end) if not __debug__ else None

def exit(*arg):
	print(*arg)
	sys.exit()

class SparseTable:

	def __init__(self, n, func, default_value):
		self._size = n
		self.func = func
		self.default_value = default_value
		self.log2 = [0 for i in range(n + 1)]
		for i in range(2, n + 1):
			self.log2[i] = self.log2[i >> 1] + 1
		self.table = [[default_value for i in range(n)] for j in range(self.log2[n] + 1)]

	@property
	def size(self):
		return self._size

	def __getitem__(self, i):
		assert i < self._size
		return self.table[0][i]

	def __str__(self):
		return str(self.table[0])

	def set(self, i, val):
		assert i < self._size
		self.table[0][i] = (val, val)

	def build(self):
		for j in range(self.log2[self._size]):
			w = 1 << j
			for i in range(self._size - (w << 1) + 1):
				self.table[j + 1][i] = self.func(self.table[j][i], self.table[j][i + w])

	def fold(self, l, r):
		if r - l < 1:
			return self.default_value
		assert l < self._size and r <= self._size
		j = self.log2[r - l]
		return self.func(self.table[j][l], self.table[j][r - (1 << j)])

	def max(self, l, r):
		return self.fold(l, r)[0]

	def min(self, l, r):
		return self.fold(l, r)[1]

class UnionFind:

	def __init__(self, n):
		self._data = [-1] * n

	def unite(self, x: int, y: int) -> bool:
		x = self.root(x)
		y = self.root(y)
		if x == y:
			return False
		elif self._data[x] > self._data[y]:
			(x, y) = (y, x)
		self._data[x] += self._data[y]
		self._data[y] = x
		return True

	def root(self, x: int) -> int:
		while self._data[x] >= 0:
			x = self._data[x]
		return x

	def same(self, x: int, y: int) -> bool:
		return self.root(x) == self.root(y)

	def size(self, x: int) -> int:
		return -self._data[self.root(x)]

def generate_testcase():
	N = 200000
	K = 10000
	with open('in_1.txt', 'w') as f:
		print(N, K, file=f)
		a = [i for i in range(N)]
		random.shuffle(a)
		print(*a, file=f)

def bruteforce(N, K, P):
	s = set()
	for i in range(N - K + 1):
		d = deepcopy(P)
		d[i:i + K] = sorted(d[i:i + K])
		s.add(''.join(list(map(str, d))))
	return len(s)

def main():
	(N, K) = mi()
	P = lmi()

	def func(x: tuple, y: tuple):
		return (max(x[0], y[0]), min(x[1], y[1]))
	spt = SparseTable(N, func, (int(-1000000000.0), int(1000000000.0)))
	for (i, val) in enumerate(P):
		spt.set(i, val)
	spt.build()
	uf = UnionFind(N - K + 1)
	right = 1
	left = 0
	ans = 0
	s = []
	while left < N - K + 1:
		while right < N and (right <= left or P[right - 1] < P[right]):
			right += 1
		if right - left >= K:
			s.append(left)
		if left == right:
			right += 1
		left += 1
	if len(s) >= 2:
		for i in range(1, len(s)):
			uf.unite(s[0], s[i])
	for i in range(N - K):
		if P[i] == spt.min(i, i + K + 1) and spt.max(i, i + K + 1) == P[i + K]:
			uf.unite(i, i + 1)
	for i in range(N - K + 1):
		if uf.root(i) == i:
			ans += 1
	print(ans)
	return
main()


import sys
input = sys.stdin.readline

def I():
	return int(input())

def MI():
	return map(int, input().split())

def LI():
	return list(map(int, input().split()))

def main():
	mod = 10 ** 9 + 7
	inf = 10 ** 6
	(N, K) = MI()
	P = LI()
	inf = 10 ** 6

	class SegTree:

		def __init__(self, N, ide, segfunc=min):
			self.ide_ele = ide
			self.segfunc = segfunc
			self.num = 2 ** (N - 1).bit_length()
			self.seg = [self.ide_ele] * 2 * self.num

		def setL(self, init_val):
			for i in range(N):
				self.seg[i + self.num - 1] = init_val[i]
			for i in range(self.num - 2, -1, -1):
				self.seg[i] = self.segfunc(self.seg[2 * i + 1], self.seg[2 * i + 2])

		def update(self, k, x):
			k += self.num - 1
			self.seg[k] = x
			while k:
				k = (k - 1) // 2
				self.seg[k] = self.segfunc(self.seg[k * 2 + 1], self.seg[k * 2 + 2])

		def query(self, p, q):
			if q <= p:
				return self.ide_ele
			p += self.num - 1
			q += self.num - 2
			res = self.ide_ele
			while q - p > 1:
				if p & 1 == 0:
					res = self.segfunc(res, self.seg[p])
				if q & 1 == 1:
					res = self.segfunc(res, self.seg[q])
					q -= 1
				p = p // 2
				q = (q - 1) // 2
			if p == q:
				res = self.segfunc(res, self.seg[p])
			else:
				res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
			return res
	ans = 1
	mseg = SegTree(N, inf, min)
	Mseg = SegTree(N, -1, max)
	mseg.setL(P)
	Mseg.setL(P)
	S = [0] * (N + 1)
	for i in range(N - 1):
		if P[i] < P[i + 1]:
			S[i + 1] = 1
	for i in range(N):
		S[i + 1] += S[i]
	m = min(P[:K])
	M = max(P[:K])
	cnt = 0
	if S[K] == K:
		cnt += 1
	for i in range(K, N):
		if m == P[i - K] and P[i] > M:
			m = mseg.query(i - K + 1, i + 1)
			M = P[i]
		else:
			m = mseg.query(i - K + 1, i + 1)
			M = Mseg.query(i - K + 1, i + 1)
			if cnt == 0:
				ans += 1
			elif S[i] - S[i - K + 1] != K - 1:
				ans += 1
			if S[i] - S[i - K + 1] == K - 1:
				cnt += 1
	print(ans)
main()


def examA():
	N = I()
	ans = 0
	print(ans)
	return

def examB():

	class UnionFind:

		def __init__(self, n):
			self.parent = [-1 for _ in range(n)]

		def find(self, x):
			if self.parent[x] < 0:
				return x
			else:
				self.parent[x] = self.find(self.parent[x])
				return self.parent[x]

		def unite(self, x, y):
			(x, y) = (self.find(x), self.find(y))
			if x == y:
				return False
			else:
				if self.size(x) < self.size(y):
					(x, y) = (y, x)
				self.parent[x] += self.parent[y]
				self.parent[y] = x

		def same(self, x, y):
			return self.find(x) == self.find(y)

		def size(self, x):
			x = self.find(x)
			return -self.parent[x]

		def is_root(self, x):
			return self.parent[x] < 0

		def roots(self):
			return [i for (i, x) in enumerate(self.parent) if x < 0]

		def members(self, x):
			root = self.find(x)
			return [i for i in range(self.n) if self.find(i) == root]

		def group_count(self):
			return len(self.roots())

		def all_group_members(self):
			return {r: self.members(r) for r in self.roots()}

	class segment_:

		def __init__(self, A, n, segfunc, ide_ele):
			self.ide_ele = ide_ele
			self.num = 1 << (n - 1).bit_length()
			self.seg = [self.ide_ele] * 2 * self.num
			self.segfunc = segfunc
			for i in range(n):
				self.seg[i + self.num] = A[i]
			for i in range(self.num - 1, 0, -1):
				self.seg[i] = self.segfunc(self.seg[2 * i], self.seg[2 * i + 1])

		def update(self, k, r):
			k += self.num
			self.seg[k] = r
			while k:
				k >>= 1
				self.seg[k] = self.segfunc(self.seg[k * 2], self.seg[k * 2 + 1])

		def update1(self, k):
			k += self.num
			self.seg[k] += 1
			while k:
				k >>= 1
				self.seg[k] = self.segfunc(self.seg[k * 2], self.seg[k * 2 + 1])

		def updateneg1(self, k):
			k += self.num
			self.seg[k] -= 1
			while k:
				k >>= 1
				self.seg[k] = self.segfunc(self.seg[k * 2], self.seg[k * 2 + 1])

		def query(self, p, q):
			if q < p:
				return self.ide_ele
			p += self.num
			q += self.num
			res = self.ide_ele
			while p < q:
				if p & 1 == 1:
					res = self.segfunc(res, self.seg[p])
					p += 1
				if q & 1 == 1:
					q -= 1
					res = self.segfunc(res, self.seg[q])
				p >>= 1
				q >>= 1
			return res
	(N, K) = LI()
	P = LI()
	Seg_min = segment_(P, N, lambda a, b: min(a, b), inf)
	Seg_max = segment_(P, N, lambda a, b: max(a, b), -inf)
	DL = defaultdict(bool)
	DR = defaultdict(bool)
	for i in range(N - K + 1):
		cur = Seg_min.query(i, i + K)
		if cur == P[i]:
			DL[i] = True
		cur = Seg_max.query(i, i + K)
		if cur == P[i + K - 1]:
			DR[i + K - 1] = True
	uf = UnionFind(N)
	bigger = [False] * N
	skip = []
	for i in range(N - 1):
		if P[i + 1] > P[i]:
			bigger[i] = True
	cur = sum(bigger[:K - 1])
	if cur == K - 1:
		skip.append(0)
	for i in range(N - K):
		if bigger[i + K - 1]:
			cur += 1
		if bigger[i]:
			cur -= 1
		if cur == K - 1:
			skip.append(i + 1)
	for i in range(len(skip) - 1):
		uf.unite(skip[i], skip[i + 1])
	for i in range(N - K):
		if DL[i] and DR[i + K]:
			uf.unite(i, i + 1)
	ans = set()
	for i in range(N - K + 1):
		cur = uf.find(i)
		ans.add(cur)
	print(len(ans))
	return

def examC():
	ans = 0
	print(ans)
	return

def examD():
	ans = 0
	print(ans)
	return

def examE():
	ans = 0
	print(ans)
	return

def examF():
	ans = 0
	print(ans)
	return
import sys, copy, bisect, itertools, heapq, math, random
from heapq import heappop, heappush, heapify
from collections import Counter, defaultdict, deque

def I():
	return int(sys.stdin.readline())

def LI():
	return list(map(int, sys.stdin.readline().split()))

def LSI():
	return list(map(str, sys.stdin.readline().split()))

def LS():
	return sys.stdin.readline().split()

def SI():
	return sys.stdin.readline().strip()
global mod, mod2, inf, alphabet, _ep
mod = 10 ** 9 + 7
mod2 = 998244353
inf = 10 ** 18
_ep = 10 ** (-12)
alphabet = [chr(ord('a') + i) for i in range(26)]
examB()


import heapq
(N, K) = map(int, input().split())
P = list(map(int, input().split()))
minlis = []
maxlis = []
endflag = [False] * N
ans = 1
for i in range(K):
	heapq.heappush(minlis, P[i])
	heapq.heappush(maxlis, -1 * P[i])
for i in range(N - K):
	flag = False
	endflag[P[i]] = True
	if minlis[0] != P[i]:
		flag = True
	while endflag[minlis[0]]:
		heapq.heappop(minlis)
	if P[i + K] <= -1 * maxlis[0]:
		flag = True
	while endflag[-1 * maxlis[0]]:
		heapq.heappop(maxlis)
	heapq.heappush(minlis, P[i + K])
	heapq.heappush(maxlis, -1 * P[i + K])
	if flag:
		ans += 1
kaburi = 0
P.append(-2)
now = 0
nmax = -1
for i in range(N + 1):
	if nmax < P[i]:
		now += 1
		nmax = P[i]
	else:
		if now >= K:
			kaburi += 1
		now = 1
		nmax = P[i]
if kaburi >= 2:
	print(ans - kaburi + 1)
else:
	print(ans)


import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10 ** 9))
from queue import deque
from collections import defaultdict
(n, k) = map(int, input().split())
p = list(map(int, input().split()))
count = 0
q = deque([])
maxq = deque([])
ren = 0
prev = -1
es = defaultdict(set)
slist = []
for (i, num) in enumerate(p):
	if i >= k:
		m = p[q[0]]
		M = p[maxq[0]]
		if num > M and m == p[i - k]:
			count += 1
			es[i - k].add(i - k + 1)
			es[i - k + 1].add(i - k)
	if prev < num:
		ren += 1
		prev = num
		if ren >= k - 1:
			slist.append(i - k + 1)
	else:
		ren = 0
		prev = num
	while q and p[q[-1]] > num:
		q.pop()
	q.append(i)
	if q[0] <= i - k:
		q.popleft()
	while maxq and p[maxq[-1]] < num:
		maxq.pop()
	maxq.append(i)
	if maxq[0] <= i - k:
		maxq.popleft()
if len(slist) >= 2:
	for i in range(len(slist) - 1):
		es[slist[i]].add(slist[i + 1])
		es[slist[i + 1]].add(slist[i])
ans = 0
seen = [False] * n
for i in range(n - k + 1):
	if seen[i]:
		continue
	ans += 1
	q = [i]
	seen[i] = True
	while q:
		u = q.pop()
		for v in es[u]:
			if not seen[v]:
				q.append(v)
				seen[v] = True
print(ans)


import sys
from itertools import accumulate

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

def list2d(a, b, c):
	return [[c] * b for i in range(a)]

def list3d(a, b, c, d):
	return [[[d] * c for j in range(b)] for i in range(a)]

def list4d(a, b, c, d, e):
	return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]

def ceil(x, y=1):
	return int(-(-x // y))

def INT():
	return int(input())

def MAP():
	return map(int, input().split())

def LIST(N=None):
	return list(MAP()) if N is None else [INT() for i in range(N)]

def Yes():
	print('Yes')

def No():
	print('No')

def YES():
	print('YES')

def NO():
	print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

class SegTree:

	def __init__(self, n, func, intv, A=[]):
		self.n = n
		self.func = func
		self.intv = intv
		n2 = 1
		while n2 < n:
			n2 <<= 1
		self.n2 = n2
		self.tree = [self.intv] * (n2 << 1)
		if A:
			for i in range(n):
				self.tree[n2 + i] = A[i]
			for i in range(n2 - 1, -1, -1):
				self.tree[i] = self.func(self.tree[i * 2], self.tree[i * 2 + 1])

	def update(self, i, x):
		i += self.n2
		self.tree[i] = x
		while i > 0:
			i >>= 1
			self.tree[i] = self.func(self.tree[i * 2], self.tree[i * 2 + 1])

	def query(self, a, b):
		l = a + self.n2
		r = b + self.n2
		s = self.intv
		while l < r:
			if r & 1:
				r -= 1
				s = self.func(s, self.tree[r])
			if l & 1:
				s = self.func(s, self.tree[l])
				l += 1
			l >>= 1
			r >>= 1
		return s

	def get(self, i):
		return self.tree[i + self.n2]

	def all(self):
		return self.tree[1]
(N, K) = MAP()
A = LIST()
stmin = SegTree(N, min, INF, A)
stmax = SegTree(N, max, -INF, A)
total = N - K + 1
dup = 0
for i in range(N - K):
	mn = stmin.query(i, i + K + 1)
	mx = stmax.query(i, i + K + 1)
	if mn == A[i] and mx == A[i + K]:
		dup += 1
B = [0] * N
for i in range(N - 1):
	if A[i] < A[i + 1]:
		B[i + 1] = 1
B = list(accumulate(B))
prev = INF
for i in range(N - K + 1):
	if B[i + K - 1] - B[i] == K - 1:
		if prev + K - 1 < i:
			dup += 1
		prev = i
print(total - dup)


from collections import deque
import itertools
(N, K) = map(int, input().split())
p = list(map(int, input().split()))
deq = deque()
min_val = [0] * (N - K + 1)
for i in range(N):
	while deq and p[deq[-1]] >= p[i]:
		deq.pop()
	deq.append(i)
	if i - K + 1 >= 0:
		min_val[i - K + 1] = p[deq[0]]
		if deq[0] == i - K + 1:
			deq.popleft()
deq = deque()
max_val = [0] * (N - K + 1)
for i in range(N):
	while deq and p[deq[-1]] <= p[i]:
		deq.pop()
	deq.append(i)
	if i - K + 1 >= 0:
		max_val[i - K + 1] = p[deq[0]]
		if deq[0] == i - K + 1:
			deq.popleft()
incr = [1 if x < y else 0 for (x, y) in zip(p, p[1:])]
incr_cum = [0] + list(itertools.accumulate(incr))
is_stable = [y - x == K - 1 for (x, y) in zip(incr_cum, incr_cum[K - 1:])]
cnt = 0
preL = -1
prerange_min = -2
sortMatchCnt = 0
for i in range(N - K + 1):
	range_min = min_val[i]
	range_max = max_val[i]
	l = p[i]
	r = p[i + K - 1]
	sortMatchFlg = False
	if is_stable[i]:
		sortMatchCnt += 1
		sortMatchFlg = True
	if preL == prerange_min and r == range_max or sortMatchFlg:
		pass
	else:
		cnt += 1
	preL = l
	prerange_min = range_min
if sortMatchCnt >= 1:
	print(cnt + 1)
else:
	print(cnt)


(n, k) = list(map(int, input().split()))
xs = list(map(int, input().split()))
from collections import deque

def slide_max(k, l):
	rs = []
	dq = deque()
	for (i, x) in enumerate(l):
		while True:
			if not len(dq):
				dq.append(i)
				break
			lxi = dq[-1]
			if x < l[lxi]:
				dq.append(i)
				break
			dq.pop()
		if i + 1 < k:
			continue
		sxi = dq[0]
		rs.append(l[sxi])
		if sxi == i + 1 - k:
			dq.popleft()
	return rs

def slide_min(k, l):
	rs = []
	dq = deque()
	for (i, x) in enumerate(l):
		while True:
			if not len(dq):
				dq.append(i)
				break
			lxi = dq[-1]
			if x > l[lxi]:
				dq.append(i)
				break
			dq.pop()
		if i + 1 < k:
			continue
		sxi = dq[0]
		rs.append(l[sxi])
		if sxi == i + 1 - k:
			dq.popleft()
	return rs
(maxs, mins) = (slide_max(k, xs), slide_min(k, xs))
(aa, bb) = (xs[:k], xs[k:])
(b, nb, bx) = (aa[0], aa[1], aa[-1])
ba = None
c = 1
for a in aa:
	if ba == None:
		ba = a
		continue
	if a > ba:
		c += 1
	else:
		c = 1
	ba = a
rok = False
if c == k:
	rok = True
r = 1
bs = xs[0]
for (i, (s, x)) in enumerate(zip(xs[1:], bb)):
	if x > bx:
		c = min(c + 1, k)
	else:
		c = 1
	bx = x
	if c == k:
		if not rok:
			r += 1
		rok = True
		continue
	if x != maxs[i + 1]:
		r += 1
	elif bs != mins[i]:
		r += 1
	bs = s
print(r)


from collections import deque

def MI():
	return map(int, input().split())

def LI():
	return [int(i) for i in input().split()]
(n, k) = MI()
a = LI()

def slidmin(a, k):
	n = len(a)
	b = [0 for i in range(n - k + 1)]
	q = deque()
	for i in range(k):
		while q and a[q[-1]] >= a[i]:
			q.pop()
		q.append(i)
	b[0] = a[q[0]]
	s = len(q)
	for i in range(k, n):
		while q and a[q[-1]] >= a[i]:
			q.pop()
			s -= 1
		q.append(i)
		s += 1
		if q[0] <= i - k:
			q.popleft()
			s -= 1
		b[i - k + 1] = a[q[0]]
	return b
m = slidmin(a, k)
M = [-i for i in slidmin([-i for i in a], k)]
ans = 1
p = -1
c = 0
for i in range(k):
	if p < a[i]:
		c += 1
	else:
		c = 1
	p = a[i]
fl = True if c == k else False
for i in range(n - k):
	if p < a[i + k]:
		c += 1
	else:
		c = 1
	p = a[i + k]
	inc = 1
	if c == k:
		if fl:
			inc = 0
		fl = True
	if a[i] == m[i] and a[i + k] == M[i + 1]:
		inc = 0
	ans += inc
print(ans)


import sys
from collections import deque
import bisect
import copy
import heapq
import itertools
import math
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7

def read_values():
	return map(int, input().split())

def read_index():
	return map(lambda x: int(x) - 1, input().split())

def read_list():
	return list(read_values())

def read_lists(N):
	return [read_list() for n in range(N)]

def main():
	(N, K) = read_values()
	A = read_list()
	S = []
	T = []
	D = deque()
	C = 0
	for k in range(K):
		a = A[k]
		heapq.heappush(S, (a, k))
		heapq.heappush(T, (-a, k))
		if k > 0:
			c = 1 if A[k - 1] > A[k] else 0
			D.append(c)
			C += c
	r = 0
	F = True if C == 0 else False
	res = 0 if F else 1
	for i in range(N - K):
		C -= D.popleft()
		c = 1 if A[K + i - 1] > A[K + i] else 0
		D.append(c)
		C += c
		out_a = A[i]
		in_a = A[K + i]
		heapq.heappush(T, (-in_a, K + i))
		while T[0][1] <= i:
			heapq.heappop(T)
		if C == 0:
			F = True
		elif not (T[0][0] == -in_a and S[0][0] == out_a):
			res += 1
		heapq.heappush(S, (in_a, K + i))
		while S[0][1] <= i:
			heapq.heappop(S)
	if F:
		res += 1
	print(res)
main()


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)


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
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
(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)


inpl = lambda : list(map(int, input().split()))
INF = 2 ** 31 - 1

class SegmentTree:

	def __init__(self, value, N=0, comp=lambda x, y: x <= y, reverse=False):
		M = max(len(value), N)
		N = 2 ** (len(bin(M)) - 3)
		if N < M:
			N *= 2
		self.N = N
		self.node = [0] * (2 * N - 1)
		self.reverse = reverse
		for i in range(N):
			self.node[N - 1 + i] = i
		self.value = [None] * N
		for (i, v) in enumerate(value):
			self.value[i] = v
		self.comp = lambda x, y: True if y is None else False if x is None else comp(x, y) ^ reverse
		for i in range(N - 2, -1, -1):
			(left_i, right_i) = (self.node[2 * i + 1], self.node[2 * i + 2])
			(left_v, right_v) = (self.value[left_i], self.value[right_i])
			if self.comp(left_v, right_v):
				self.node[i] = left_i
			else:
				self.node[i] = right_i

	def set_input(self, n, v):
		self.value[n] = v
		i = self.N - 1 + n
		while i > 0:
			i = (i - 1) // 2
			(left_i, right_i) = (self.node[2 * i + 1], self.node[2 * i + 2])
			(left_v, right_v) = (self.value[left_i], self.value[right_i])
			if self.comp(left_v, right_v):
				new_i = left_i
			else:
				new_i = right_i
			if new_i == self.node[i] and new_i != n:
				break
			else:
				self.node[i] = new_i

	def get_input(self, n):
		if n is None:
			return None
		else:
			return self.value[n]

	def get_output(self, l, r):
		L = l + self.N
		R = r + self.N
		if self.reverse:
			s = -INF
		else:
			s = INF
		while L < R:
			if R & 1:
				R -= 1
				if self.reverse:
					s = max(s, self.value[self.node[R - 1]])
				else:
					s = min(s, self.value[self.node[R - 1]])
			if L & 1:
				if self.reverse:
					s = max(s, self.value[self.node[L - 1]])
				else:
					s = min(s, self.value[self.node[L - 1]])
				L += 1
			L >>= 1
			R >>= 1
		return s

	def get_output_index(self, a=0, b=-1, k=0, l=0, r=-1):
		if b < 0:
			b = self.N
		if r < 0:
			r = self.N
		if a <= l and r <= b:
			return self.node[k]
		elif r <= a or b <= l:
			return None
		else:
			left_i = self.get_output_index(a, b, 2 * k + 1, l, (l + r) // 2)
			right_i = self.get_output_index(a, b, 2 * k + 2, (l + r) // 2, r)
			(left_v, right_v) = (self.get_input(left_i), self.get_input(right_i))
			if left_v is None and right_v is None:
				return None
			elif self.comp(left_v, right_v):
				return left_i
			else:
				return right_i

def get_sequence(arr):
	if len(arr) == 0:
		return ([], [])
	elements = []
	nums = []
	n = 1
	prev = arr[0]
	for c in arr[1:]:
		if c == prev:
			n += 1
		else:
			elements.append(prev)
			nums.append(n)
			prev = c
			n = 1
	elements.append(prev)
	nums.append(n)
	return (elements, nums)
(N, K) = inpl()
P = inpl()
minseg = SegmentTree(P)
maxseg = SegmentTree(P, reverse=True)
ans = 1
for i in range(N - K):
	if P[i] < minseg.get_output(i + 1, i + K) and P[i + K] > maxseg.get_output(i + 1, i + K):
		pass
	else:
		ans += 1
ordered = [P[i] < P[i + 1] for i in range(N - 1)]
(elements, nums) = get_sequence(ordered)
nums = nums[(elements[0] + 1) % 2::2]
unchanged = len(list(filter(lambda x: x >= K - 1, nums)))
if unchanged > 1:
	ans -= unchanged - 1
print(ans)


import math

def main():
	(N, K) = map(int, input().split())
	P = list(map(int, input().split()))
	seq = 1
	for i in range(K - 1):
		if P[i] < P[i + 1]:
			seq += 1
		else:
			seq = 1
	has_orig = seq == K
	ln = int(math.log(K, 2))
	dp1 = [[0] * N for _ in range(ln + 1)]
	dp2 = [[0] * N for _ in range(ln + 1)]
	dp1[0] = P
	dp2[0] = P
	for k in range(ln):
		for i in range(N - 2 ** k):
			dp1[k + 1][i] = min(dp1[k][i], dp1[k][i + 2 ** k])
			dp2[k + 1][i] = max(dp2[k][i], dp2[k][i + 2 ** k])
	rmq = [float('inf')] * (N - K + 1)
	rMq = [0] * (N - K + 1)
	for i in range(N - K + 1):
		idx = i
		for k in range(ln + 1)[::-1]:
			if K & 2 ** k:
				rmq[i] = min(rmq[i], dp1[k][idx])
				rMq[i] = max(rMq[i], dp2[k][idx])
				idx += 2 ** k
	ans = 1
	for i in range(N - K):
		if P[i + K - 1] < P[i + K]:
			seq += 1
		else:
			seq = 1
		if seq >= K:
			if not has_orig:
				has_orig = True
				ans += 1
			continue
		if P[i] != rmq[i] or P[i + K] < rMq[i]:
			ans += 1
	print(ans)
main()


class SegmentTree:

	def __init__(self, L, op, ide):
		self.op = op
		self.ide = ide
		self.sz = len(L)
		self.n = 1
		self.s = 1
		for i in range(1000):
			self.n *= 2
			self.s += 1
			if self.n >= self.sz:
				break
		self.node = [self.ide] * (2 * self.n - 1)
		for i in range(self.sz):
			self.node[i + self.n - 1] = L[i]
		for i in range(self.n - 2, -1, -1):
			self.node[i] = self.op(self.node[i * 2 + 1], self.node[i * 2 + 2])

	def add(self, a, x):
		k = a + self.n - 1
		self.node[k] += x
		for i in range(1000):
			k = (k - 1) // 2
			self.node[k] = self.op(self.node[2 * k + 1], self.node[2 * k + 2])
			if k <= 0:
				break

	def substitute(self, a, x):
		k = a + self.n - 1
		self.node[k] = x
		for i in range(1000):
			k = (k - 1) // 2
			self.node[k] = self.op(self.node[2 * k + 1], self.node[2 * k + 2])
			if k <= 0:
				break

	def get_one(self, a):
		k = a + self.n - 1
		return self.node[k]

	def get(self, l, r):
		res = self.ide
		n = self.n
		if self.sz <= r or 0 > l:
			print('ERROR: the indice are wrong.')
			return False
		for i in range(self.s):
			count = 2 ** i - 1
			a = (r + 1) // n
			b = (l - 1) // n
			if a - b == 3:
				res = self.op(self.node[count + b + 1], res)
				res = self.op(self.node[count + b + 2], res)
				right = a * n
				left = (b + 1) * n - 1
				break
			if a - b == 2:
				res = self.op(self.node[count + b + 1], res)
				right = a * n
				left = (b + 1) * n - 1
				break
			n = n // 2
		n1 = n // 2
		for j in range(i + 1, self.s):
			count = 2 ** j - 1
			a = (left + 1) // n1
			b = (l - 1) // n1
			if a - b == 2:
				res = self.op(self.node[count + b + 1], res)
				left = (b + 1) * n1 - 1
			n1 = n1 // 2
		n1 = n // 2
		for j in range(i + 1, self.s):
			count = 2 ** j - 1
			a = (r + 1) // n1
			b = (right - 1) // n1
			if a - b == 2:
				res = self.op(self.node[count + b + 1], res)
				right = a * n1
			n1 = n1 // 2
		return res
(N, K) = list(map(int, input().split()))
P = list(map(int, input().split()))
count = 0
Tag = [0] * N
for i in range(1, N):
	if P[i] < P[i - 1]:
		count += 1
	Tag[i] = count
ST1 = SegmentTree(P, max, -10 ** 27)
ST2 = SegmentTree(P, min, 10 ** 27)
ans = 0
same_flag = False
for i in range(N - K + 1):
	if Tag[i + K - 1] == Tag[i]:
		if not same_flag:
			same_flag = True
			ans += 1
	elif i > 0:
		M = ST1.get(i, i + K - 2)
		m = ST2.get(i, i + K - 2)
		if not (P[i - 1] < m and P[i + K - 1] > M):
			ans += 1
	else:
		ans += 1
print(ans)


from heapq import heappush, heappop
(n, k) = map(int, input().split())
p = list(map(int, input().split()))
cnt = 1
flag = [1] * n
for i in range(1, n):
	if p[i] > p[i - 1]:
		cnt += 1
		flag[i] = cnt
	else:
		cnt = 1
h = flag.count(k)
if h != 0:
	h -= 1
lst_m = []
lst_M = []
for i in range(k):
	heappush(lst_m, p[i])
	heappush(lst_M, -p[i])
data_m = []
data_M = []
count = 0
for i in range(n - k):
	m = lst_m[0]
	M = lst_M[0]
	heappush(lst_m, p[k + i])
	heappush(lst_M, -p[k + i])
	heappush(data_m, p[i])
	heappush(data_M, -p[i])
	if p[i] == lst_m[0]:
		while data_m[0] == lst_m[0]:
			heappop(data_m)
			heappop(lst_m)
			if not data_m:
				break
		if -p[k + i] == lst_M[0]:
			count += 1
	if -p[i] == lst_M[0]:
		while data_M[0] == lst_M[0]:
			heappop(data_M)
			heappop(lst_M)
			if not data_M:
				break
print(n - k + 1 - count - h)


import math
import os
import sys
if os.getenv('LOCAL'):
	sys.stdin = open('_in.txt', 'r')
sys.setrecursionlimit(2147483647)
INF = float('inf')
IINF = 10 ** 18
MOD = 10 ** 9 + 7

class SparseTable:

	def __init__(self, values, fn):
		self._values = values
		self._fn = fn
		self._table = self._build(values, fn)
		self._msb = [0] * (len(values) + 1)
		for i in range(2, len(values) + 1):
			self._msb[i] = self._msb[i >> 1] + 1

	@staticmethod
	def _build(values, fn):
		size = int(math.log(len(values), 2)) + 1
		st = [[0] * size for _ in range(len(values))]
		for i in range(len(values)):
			st[i][0] = i
		for p in range(1, size):
			for i in range(len(values)):
				q = min(i + (1 << p - 1), len(values) - 1)
				l = st[i][p - 1]
				r = st[q][p - 1]
				if values[l] == fn(values[l], values[r]):
					st[i][p] = l
				else:
					st[i][p] = r
		return st

	def get(self, a, b):
		if b <= a:
			return None
		p = self._msb[b - a]
		return self._fn(self._values[self._table[a][p]], self._values[self._table[b - (1 << p)][p]])
(N, K) = list(map(int, sys.stdin.readline().split()))
P = list(map(int, sys.stdin.readline().split()))
dp = [1] * N
for i in range(1, N):
	if P[i - 1] < P[i]:
		dp[i] = dp[i - 1] + 1
ans = N - K + 1
asc_cnt = 0
st_max = SparseTable(P, max)
st_min = SparseTable(P, min)
for r in range(K, N):
	l = r - K
	if st_min.get(l, r) == P[l] and st_max.get(l + 1, r + 1) == P[r]:
		ans -= 1
	elif dp[r] >= K:
		ans -= 1
		asc_cnt += 1
if dp[K - 1] >= K:
	ans -= 1
	asc_cnt += 1
if asc_cnt > 0:
	ans += 1
print(ans)


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)


class BinaryIndexedTree:

	def __init__(self, n):
		self.n = n
		self.tree = [0 for _ in range(n + 1)]

	def sum(self, index):
		res = 0
		while index:
			res += self.tree[index]
			index -= index & -index
		return res

	def add(self, index, x):
		while index <= self.n:
			self.tree[index] += x
			index += index & -index

	def bisect_left(self, x):
		if x <= 0:
			return 0
		(res, tmp) = (0, 2 ** (self.n.bit_length() - 1))
		while tmp:
			if res + tmp <= self.n and self.tree[res + tmp] < x:
				x -= self.tree[res + tmp]
				res += tmp
			tmp >>= 1
		return res + 1
(N, K) = map(int, input().split())
P = list(map(lambda x: int(x) + 1, input().split()))
bit = BinaryIndexedTree(N + 1)
count = 1
for i in range(K):
	bit.add(P[i], 1)
for i in range(N - K):
	mi = bit.bisect_left(1)
	ma = bit.bisect_left(K)
	if P[i] != mi or P[K + i] < ma:
		count += 1
	bit.add(P[i], -1)
	bit.add(P[K + i], 1)
inc = 1
incseq = 0
for i in range(N - 1):
	if P[i] < P[i + 1]:
		inc += 1
		if inc == K:
			incseq += 1
	else:
		inc = 1
print(count - max(0, incseq - 1))


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
	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)


(n, k) = map(int, input().split())
p = list(map(int, input().split()))

class SegmentTree:

	def __init__(self, n, func=lambda x, y: min(x, y), ide=float('inf')):
		self.n = 2 ** (n - 1).bit_length()
		self.data = [ide] * (self.n * 2)
		(self.func, self.ide) = (func, ide)

	def build(self, data):
		for (i, x) in enumerate(data):
			self.data[self.n + i] = x
		for i in range(self.n - 1, 0, -1):
			self.data[i] = self.func(self.data[i * 2], self.data[i * 2 + 1])

	def update(self, i, x):
		i += self.n
		self.data[i] = x
		while i > 1:
			i //= 2
			self.data[i] = self.func(self.data[i * 2], self.data[i * 2 + 1])

	def query(self, l, r):
		l += self.n
		r += self.n
		res = self.ide
		while l < r:
			if l & 1:
				res = self.func(res, self.data[l])
				l += 1
			if r & 1:
				res = self.func(res, self.data[r - 1])
			l //= 2
			r //= 2
		return res

	def get(self, i):
		return self.data[self.n + i]
(minst, maxst) = (SegmentTree(n), SegmentTree(n, lambda x, y: max(x, y), -float('inf')))
minst.build(p)
maxst.build(p)
ans = n - k + 1
for i in range(n - k):
	j = i + k
	if minst.query(i, j + 1) == p[i] and maxst.query(i, j + 1) == p[j]:
		ans -= 1
srted = [1] * n
cnt = 0
for i in range(n):
	if p[i] > p[i - 1]:
		srted[i] = srted[i - 1] + 1
	if srted[i] == k:
		cnt += 1
if cnt > 1:
	ans -= cnt - 1
print(ans)


from collections import deque

def sliding_minima(a, k):
	dq = deque()
	l = r = 0
	ret = []
	for (i, item) in enumerate(a):
		while dq and a[dq[-1]] >= a[i]:
			dq.pop()
		dq.append(i)
		if i < k - 1:
			continue
		if dq[0] == i - k:
			dq.popleft()
		ret.append(a[dq[0]])
	return ret

def sliding_maxima(a, k):
	dq = deque()
	l = r = 0
	ret = []
	for (i, item) in enumerate(a):
		while dq and a[dq[-1]] <= a[i]:
			dq.pop()
		dq.append(i)
		if i < k - 1:
			continue
		if dq[0] == i - k:
			dq.popleft()
		ret.append(a[dq[0]])
	return ret

def is_increasing(a, k):
	increasing = [0] * len(a)
	for (i, (a1, a2)) in enumerate(zip(a, a[1:])):
		if a1 < a2:
			increasing[i + 1] = 1
	ret = [0] * (len(a) - k + 1)
	val = sum(increasing[1:k])
	if val == k - 1:
		ret[0] = 1
	for i in range(len(a) - k):
		val += increasing[i + k]
		val -= increasing[i + 1]
		if val == k - 1:
			ret[i + 1] = 1
		else:
			ret[i + 1] = 0
	return ret
(n, k) = [int(item) for item in input().split()]
a = [int(item) for item in input().split()]
minima = sliding_minima(a, k)
maxima = sliding_maxima(a, k)
increasing = is_increasing(a, k)
ans = n - k + 1
if increasing[0]:
	ans -= 1
for (l, r, minima, maxima, inc) in zip(a, a[k:], minima[1:], maxima, increasing[1:]):
	if l < minima and r > maxima or inc:
		ans -= 1
if sum(increasing) > 0:
	ans += 1
print(ans)


import sys
input = sys.stdin.buffer.readline
(N, K) = map(int, input().split())
p = list(map(int, input().split()))

class SegTree:

	def segfunc(self, x, y):
		u = min(x[0], y[0])
		v = max(x[1], y[1])
		return (u, v)

	def __init__(self, n, ide_ele, init_val):
		self.ide_ele = ide_ele
		self.num = 2 ** (n - 1).bit_length()
		self.seg = [self.ide_ele] * 2 * self.num
		for i in range(n):
			self.seg[i + self.num - 1] = init_val[i]
		for i in range(self.num - 2, -1, -1):
			self.seg[i] = self.segfunc(self.seg[2 * i + 1], self.seg[2 * i + 2])

	def update(self, k, x):
		k += self.num - 1
		self.seg[k] = x
		while k + 1:
			k = (k - 1) // 2
			self.seg[k] = self.segfunc(self.seg[k * 2 + 1], self.seg[k * 2 + 2])

	def query(self, p, q):
		if q <= p:
			return self.ide_ele
		p += self.num - 1
		q += self.num - 2
		res = self.ide_ele
		while q - p > 1:
			if p & 1 == 0:
				res = self.segfunc(res, self.seg[p])
			if q & 1 == 1:
				res = self.segfunc(res, self.seg[q])
				q -= 1
			p = p // 2
			q = (q - 1) // 2
		if p == q:
			res = self.segfunc(res, self.seg[p])
		else:
			res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
		return res
p = [(x, x) for x in p]
seg = SegTree(N, (float('inf'), 0), p)
mini = [0] * (N - K + 1)
maxi = [0] * (N - K + 1)
for i in range(N - K + 1):
	temp = seg.query(i, i + K)
	mini[i] = temp[0]
	maxi[i] = temp[1]
dcount = 0
alsorted = 0
temp = 0
for i in range(1, N - K + 1):
	if mini[i] != mini[i - 1] and maxi[i] == p[i + K - 1][0]:
		dcount += 1
for i in range(N - 1):
	if p[i][0] < p[i + 1][0]:
		temp += 1
	else:
		temp = 0
	if temp == K - 1:
		alsorted += 1
if alsorted == 0:
	alsorted = 1
print(N - K + 1 - dcount - alsorted + 1)


import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7

class SegTree:

	def __init__(self, init_val, segfunc, ide_ele):
		n = len(init_val)
		self.segfunc = segfunc
		self.ide_ele = ide_ele
		self.num = 1 << (n - 1).bit_length()
		self.tree = [ide_ele] * 2 * self.num
		for i in range(n):
			self.tree[self.num + i] = init_val[i]
		for i in range(self.num - 1, 0, -1):
			self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

	def update(self, k, x):
		k += self.num
		self.tree[k] = x
		while k > 1:
			self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
			k >>= 1

	def query(self, left, right):
		res = self.ide_ele
		left += self.num
		right += self.num
		while left < right:
			if left & 1:
				res = self.segfunc(res, self.tree[left])
				left += 1
			if right & 1:
				res = self.segfunc(res, self.tree[right - 1])
			left >>= 1
			right >>= 1
		return res

def resolve():
	(n, k) = map(int, input().split())
	P = list(map(int, input().split()))
	seg_min = SegTree(P, lambda x, y: min(x, y), f_inf)
	seg_max = SegTree(P, lambda x, y: max(x, y), -f_inf)
	mi = seg_min.query(0, k)
	ma = seg_max.query(0, k)
	res = {(0, k - 1)}
	for i in range(1, n - k + 1):
		prev = P[i - 1]
		new = P[i + k - 1]
		if prev != mi or new < ma:
			res.add((i, i + k - 1))
		mi = seg_min.query(i, i + k)
		ma = seg_max.query(i, i + k)
	ascending = []
	head = 0
	foot = 1
	cnt = 1
	for i in range(1, n):
		if P[i - 1] < P[i]:
			cnt += 1
			foot = i
		else:
			cnt = 1
			head = i
		if cnt == k:
			ascending.append((head, foot))
			head = i
			cnt -= 1
	ans = len(res)
	flg = False
	for section in ascending:
		if section in res:
			if not flg:
				flg = True
			else:
				ans -= 1
	print(ans)
resolve()


from collections import deque

def slide_max(A, K):
	N = len(A)
	max_idx = [0] * N
	d = deque()
	for i in range(N):
		while d and d[0] <= i - K:
			d.popleft()
		while d and A[d[-1]] < A[i]:
			d.pop()
		d.append(i)
		max_idx[i] = d[0]
	return max_idx

def slide_min(A, K):
	N = len(A)
	min_idx = [0] * N
	d = deque()
	for i in range(N):
		while d and d[0] <= i - K:
			d.popleft()
		while d and A[d[-1]] > A[i]:
			d.pop()
		d.append(i)
		min_idx[i] = d[0]
	return min_idx
(N, K) = map(int, input().split())
A = list(map(int, input().split()))
larger_than_left = [1] * N
for i in range(1, N):
	if A[i] < A[i - 1]:
		larger_than_left[i] = 0
sorted_idx = set()
num = sum(larger_than_left[1:K])
if num == K - 1:
	sorted_idx.add(0)
for i in range(1, N - K + 1):
	num += larger_than_left[i + K - 1] - larger_than_left[i]
	if num == K - 1:
		sorted_idx.add(i)
max_idx = slide_max(A, K - 1)
min_idx = slide_min(A, K - 1)
ans = [] if 0 in sorted_idx else [0]
for i in range(1, N - K + 1):
	if i in sorted_idx:
		continue
	left = A[i - 1]
	right = A[i + K - 1]
	M = A[max_idx[i + K - 2]]
	m = A[min_idx[i + K - 2]]
	if m < left or right < M:
		ans.append(i)
print(len(ans) + (len(sorted_idx) > 0))


(n, k) = map(int, input().split())
p = list(map(int, input().split()))

def init(init_val):
	for i in range(n):
		MI[i + num - 1] = init_val[i]
		MA[i + num - 1] = init_val[i]
	for i in range(num - 2, -1, -1):
		MI[i] = min(MI[2 * i + 1], MI[2 * i + 2])
		MA[i] = max(MA[2 * i + 1], MA[2 * i + 2])

def update(k, x):
	k += num - 1
	MI[k] = x
	MA[k] = x
	while k + 1:
		k = (k - 1) // 2
		MI[k] = min(MI[k * 2 + 1], MI[k * 2 + 2])
		MA[k] = max(MA[k * 2 + 1], MA[k * 2 + 2])

def rangemin(p, q):
	if q <= p:
		return 1 << 100
	p += num - 1
	q += num - 2
	res = 1 << 100
	while q - p > 1:
		if p & 1 == 0:
			res = min(res, MI[p])
		if q & 1 == 1:
			res = min(res, MI[q])
			q -= 1
		p = p // 2
		q = (q - 1) // 2
	if p == q:
		res = min(res, MI[p])
	else:
		res = min(min(res, MI[p]), MI[q])
	return res

def rangemax(p, q):
	if q <= p:
		return -1
	p += num - 1
	q += num - 2
	res = -1
	while q - p > 1:
		if p & 1 == 0:
			res = max(res, MA[p])
		if q & 1 == 1:
			res = max(res, MA[q])
			q -= 1
		p = p // 2
		q = (q - 1) // 2
	if p == q:
		res = max(res, MA[p])
	else:
		res = max(max(res, MA[p]), MA[q])
	return res
num = 2 ** (n - 1).bit_length()
MI = [1 << 100] * 2 * num
MA = [-1] * 2 * num
init(p)
a = 0
l = -1
c = 0
for i in range(1, n):
	if p[i - 1] > p[i]:
		a = i
	if i >= k - 1 and a <= i - k + 1:
		if i - l > 1:
			c += 1
		l = i
ans = 1 - max(c - 1, 0)
for i in range(n):
	if i >= k:
		if rangemin(i - k + 1, i) < p[i - k] or rangemax(i - k + 1, i) > p[i]:
			ans += 1
print(ans)


class UnionFind:

	def __init__(self, N):
		self.parent = [i for i in range(N)]
		self.size = [1 for _ in range(N)]

	def find(self, x):
		if self.parent[x] == x:
			return x
		else:
			return self.find(self.parent[x])

	def union(self, x, y):
		px = self.find(x)
		py = self.find(y)
		if px == py:
			return
		if self.size[px] < self.size[py]:
			self.parent[px] = py
			self.size[py] += self.size[px]
		else:
			self.parent[py] = px
			self.size[px] += self.size[py]

	def same(self, x, y):
		return self.find(x) == self.find(y)

	def connectedNum(self, x):
		return self.size[self.find(x)]

	def is_connected(self):
		return self.connectedNum(0) == len(self.parent)

	def componentNum(self):
		par_set = set()
		for p in self.parent:
			par_set.add(self.find(p))
		return len(par_set)

class SegmentTree:

	def __init__(self, n, func, init=float('inf')):
		self.n = 2 ** (n - 1).bit_length()
		self.init = init
		self.data = [init] * (2 * self.n)
		self.func = func

	def set(self, k, v):
		self.data[k + self.n - 1] = v

	def build(self):
		for k in reversed(range(self.n - 1)):
			self.data[k] = self.func(self.data[k * 2 + 1], self.data[k * 2 + 2])

	def update(self, k, a):
		k += self.n - 1
		self.data[k] = a
		while k > 0:
			k = (k - 1) // 2
			self.data[k] = self.func(self.data[k * 2 + 1], self.data[k * 2 + 2])

	def query(self, l, r):
		L = l + self.n
		R = r + self.n
		ret = self.init
		while L < R:
			if R & 1:
				R -= 1
				ret = self.func(ret, self.data[R - 1])
			if L & 1:
				ret = self.func(ret, self.data[L - 1])
				L += 1
			L >>= 1
			R >>= 1
		return ret
(N, K) = map(int, input().split())
P = list(map(int, input().split()))
Seg_min = SegmentTree(N, min)
Seg_max = SegmentTree(N, max, 0)
for (i, p) in enumerate(P):
	Seg_min.set(i, p)
	Seg_max.set(i, p)
Seg_min.build()
Seg_max.build()
inc = [0] * (N + 1)
for i in range(N - 1):
	if P[i + 1] > P[i]:
		inc[i + 1] = 1
for i in range(N):
	if inc[i + 1] != 0:
		inc[i + 1] += inc[i]
Un = UnionFind(N - K + 1)
sorted_seg_par = None
for i in range(N - K + 1):
	if inc[i + K - 1] >= K - 1:
		if sorted_seg_par is None:
			sorted_seg_par = i
		else:
			Un.union(sorted_seg_par, i)
	elif i + 1 < N - K + 1 and P[i] == Seg_min.query(i, i + K + 1) and (P[i + K] == Seg_max.query(i, i + K + 1)):
		Un.union(i, i + 1)
print(Un.componentNum())


from heapq import heappush, heappop
(N, K) = map(int, input().split())
P = [int(i) for i in input().split()]
dp = [0] * N
dp[0] = 1
for i in range(1, N):
	if P[i] > P[i - 1]:
		dp[i] = dp[i - 1] + 1
	else:
		dp[i] = 1
ma = []
mi = []
for i in range(K):
	heappush(ma, (-P[i], i))
	heappush(mi, (P[i], i))
if dp[K - 1] == K:
	ret = 0
else:
	ret = 1
for i in range(K, N):
	heappush(ma, (-P[i], i))
	heappush(mi, (P[i], i))
	while ma[0][1] < i - K:
		heappop(ma)
	while mi[0][1] < i - K:
		heappop(mi)
	if dp[i] < K and (P[i - K] != mi[0][0] or P[i] != -ma[0][0]):
		ret += 1
if sum([dp[i] >= K for i in range(N)]) > 0:
	ret += 1
print(ret)


from collections import deque
(n, k) = map(int, input().split())
p = list(map(int, input().split()))
minList = deque()
maxList = deque()
ascList = deque()

def add_list(_k, target):
	global p
	global minList
	global maxList
	global ascList
	while len(minList) > 0 and p[minList[-1]] >= p[target]:
		minList.pop()
	minList.append(target)
	if minList[0] == target - _k:
		minList.popleft()
	while len(maxList) > 0 and p[maxList[-1]] <= p[target]:
		maxList.pop()
	maxList.append(target)
	if maxList[0] == target - _k:
		maxList.popleft()
	if target > 0 and p[target] < p[target - 1]:
		ascList.append(target - 1)
	if len(ascList) > 0 and ascList[0] == target - _k:
		ascList.popleft()
count = 0
ascend = 0
for i in range(k):
	add_list(k, i)
if len(ascList) == 0:
	ascend += 1
else:
	count += 1
for i in range(k, n):
	tail_is_max = False
	if p[i] > p[maxList[0]]:
		tail_is_max = True
	add_list(k, i)
	head_is_min = False
	if p[i - k] < p[minList[0]]:
		head_is_min = True
	if not (tail_is_max and head_is_min):
		if len(ascList) == 0:
			if ascend == 0:
				ascend += 1
		else:
			count += 1
print(count + ascend)


from collections import deque
(n, k) = map(int, input().split())
p = list(map(int, input().split()))
minp = [0] * (n - k + 1)
maxp = [0] * (n - k + 1)
q1 = deque([0])
q2 = deque([0])
for i in range(1, k):
	while p[q1[-1]] > p[i]:
		q1.pop()
		if len(q1) == 0:
			break
	while p[q2[-1]] < p[i]:
		q2.pop()
		if len(q2) == 0:
			break
	q1.append(i)
	q2.append(i)
for i in range(n - k + 1):
	minp[i] = p[q1[0]]
	maxp[i] = p[q2[0]]
	if i == n - k:
		break
	if q1[0] == i:
		q1.popleft()
	if q2[0] == i:
		q2.popleft()
	while p[q1[-1]] > p[i + k]:
		q1.pop()
		if len(q1) == 0:
			break
	while p[q2[-1]] < p[i + k]:
		q2.pop()
		if len(q2) == 0:
			break
	q1.append(i + k)
	q2.append(i + k)
d = [0] * n
d[0] = 1
for i in range(1, n):
	if p[i] > p[i - 1]:
		d[i] = d[i - 1] + 1
	else:
		d[i] = 1
ans = int(k in d)
if d[k - 1] != k:
	ans += 1
for i in range(n - k):
	if d[i + k] >= k:
		continue
	if not (p[i] == minp[i] and p[i + k] == maxp[i + 1]):
		ans += 1
print(ans)


import sys
input = sys.stdin.readline

class Segtree:

	def __init__(self, n, v, func, initial):
		self.initial = initial
		self.func = func
		self.size = 1 << n.bit_length()
		self.tree = [self.initial] * (2 * self.size)
		for i in range(n):
			self.tree[i + self.size] = v[i]
		for i in range(self.size - 1, 0, -1):
			self.tree[i] = self.func(self.tree[i * 2], self.tree[i * 2 + 1])

	def update(self, n, x):
		i = n + self.size
		self.tree[i] = x
		i >>= 1
		while i != 0:
			self.tree[i] = self.func(self.tree[i * 2], self.tree[i * 2 + 1])
			i >>= 1

	def getvalues(self, l, r):
		L = l + self.size
		R = r + self.size
		ANS = self.initial
		while L < R:
			if L & 1:
				ANS = self.func(ANS, self.tree[L])
				L += 1
			if R & 1:
				R -= 1
				ANS = self.func(ANS, self.tree[R])
			L >>= 1
			R >>= 1
		return ANS

class UnionFind:

	def __init__(self, n):
		self.v = [-1 for _ in range(n)]

	def find(self, x):
		if self.v[x] < 0:
			return x
		else:
			self.v[x] = self.find(self.v[x])
			return self.v[x]

	def unite(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if x == y:
			return
		if -self.v[x] < -self.v[y]:
			(x, y) = (y, x)
		self.v[x] += self.v[y]
		self.v[y] = x

	def root(self, x):
		return self.v[x] < 0

def main():
	(n, k) = map(int, input().split())
	p = tuple((int(x) for x in input().split()))
	tr1 = Segtree(n, p, min, 1 << 30)
	tr2 = Segtree(n, p, max, -1)
	uf = UnionFind(n)
	cont = 1
	v = None
	for i in range(1, n):
		if p[i - 1] < p[i]:
			cont += 1
		else:
			cont = 1
		if cont >= k:
			if v is None:
				v = i - k + 1
			else:
				uf.unite(v, i - k + 1)
	for i in range(n - k):
		if p[i] < tr1.getvalues(i + 1, i + k) < tr2.getvalues(i + 1, i + k) < p[i + k]:
			uf.unite(i, i + 1)
	ans = sum((uf.root(x) for x in range(n - k + 1)))
	print(ans)
main()


from collections import deque
(N, K) = map(int, input().split())
P = list(map(int, input().split()))
maxQ = deque([])
minQ = deque([])
for i in range(K):
	while maxQ:
		if P[maxQ[-1]] <= P[i]:
			maxQ.pop()
		else:
			break
	maxQ.append(i)
	if maxQ[0] == i - K:
		maxQ.popleft()
	while minQ:
		if P[minQ[-1]] >= P[i]:
			minQ.pop()
		else:
			break
	minQ.append(i)
	if minQ[0] == i - K:
		minQ.popleft()
ans = 1
hasSame = False
seq = 1
for i in range(1, K):
	if P[i - 1] < P[i]:
		seq += 1
	else:
		seq = 1
if seq >= K:
	hasSame = True
for left in range(N - K):
	right = left + K
	if P[right - 1] < P[right]:
		seq += 1
	else:
		seq = 1
	while maxQ:
		if P[maxQ[-1]] <= P[right]:
			maxQ.pop()
		else:
			break
	maxQ.append(right)
	if maxQ[0] == right - K:
		maxQ.popleft()
	if left == minQ[0] and right == maxQ[0]:
		pass
	elif seq < K:
		ans += 1
	elif not hasSame:
		hasSame = True
		ans += 1
	while minQ:
		if P[minQ[-1]] >= P[right]:
			minQ.pop()
		else:
			break
	minQ.append(right)
	if minQ[0] == right - K:
		minQ.popleft()
print(ans)


import sys

def inp():
	return int(sys.stdin.readline())

def inpl():
	return list(map(int, sys.stdin.readline().split()))

class Searchable_BIT:

	def __init__(self, N):
		self.N = N
		self.node = [0] * (self.N + 1)
		self.cnt = 0

	def add(self, a):
		x = a
		self.cnt += 1
		while x <= self.N:
			self.node[x] += 1
			x += x & -x

	def delete(self, x):
		self.cnt -= 1
		while x <= self.N:
			self.node[x] -= 1
			x += x & -x

	def count(self, x):
		tmp = 0
		while x > 0:
			tmp += self.node[x]
			x -= x & -x
		return tmp

	def get_maxval(self):
		return self.get_lower_i(self.cnt)

	def get_lower_i(self, i):
		NG = -1
		OK = self.N
		while OK - NG > 1:
			mid = (OK + NG) // 2
			if self.count(mid) >= i:
				OK = mid
			else:
				NG = mid
		return OK
(N, K) = inpl()
PP = inpl()
BIT = Searchable_BIT(N + 1)
for i in range(1, K):
	BIT.add(PP[i] + 1)
ans = [i for i in range(N - K + 1)]
cnt = 1
for i in range(N - 1):
	if PP[i] < PP[i + 1]:
		cnt += 1
	else:
		cnt = 1
	if cnt >= K:
		ans[i - K + 2] = -1
for i in range(N - K):
	(L, R) = (PP[i] + 1, PP[i + K] + 1)
	(MIN, MAX) = (BIT.get_lower_i(1), BIT.get_maxval())
	if L <= MIN and MAX <= R:
		ans[i + 1] = ans[i]
	BIT.delete(PP[i + 1] + 1)
	BIT.add(PP[i + K] + 1)
print(len(set(ans)))


import sys
input = sys.stdin.readline
(n, k) = map(int, input().split())
P = list(map(int, input().split()))
INF = 2 ** 31 - 1
N0 = 1 << (n - 1).bit_length()
seg_min = [INF] * (N0 << 1)
seg_max = [0] * (N0 << 1)

def update_min(i, x):
	i += N0
	seg_min[i] = x
	while i > 1:
		y = seg_min[i ^ 1]
		if y <= x:
			break
		i >>= 1
		seg_min[i] = x

def query_min(l, r):
	res = INF
	l += N0
	r += N0
	while l < r:
		if r & 1:
			res = min(res, seg_min[r - 1])
		if l & 1:
			res = min(res, seg_min[l])
			l += 1
		l >>= 1
		r >>= 1
	return res

def init_min(original):
	for (i, x) in enumerate(original):
		update_min(i, x)

def update_max(i, x):
	i += N0
	seg_max[i] = x
	while i > 1:
		y = seg_max[i ^ 1]
		if y >= x:
			break
		i >>= 1
		seg_max[i] = x

def query_max(l, r):
	res = 0
	l += N0
	r += N0
	while l < r:
		if r & 1:
			res = max(res, seg_max[r - 1])
		if l & 1:
			res = max(res, seg_max[l])
			l += 1
		l >>= 1
		r >>= 1
	return res

def init_max(original):
	for (i, x) in enumerate(original):
		update_max(i, x)

class UnionFind:

	def __init__(self, n):
		self.n = n
		self.parents = [-1] * n

	def find(self, x):
		if self.parents[x] < 0:
			return x
		else:
			self.parents[x] = self.find(self.parents[x])
			return self.parents[x]

	def unite(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if x == y:
			return
		if self.parents[x] > self.parents[y]:
			(x, y) = (y, x)
		self.parents[x] += self.parents[y]
		self.parents[y] = x

	def size(self, x):
		return -self.parents[self.find(x)]

	def same(self, x, y):
		return self.find(x) == self.find(y)

	def members(self, x):
		root = self.find(x)
		return [i for i in range(self.n) if self.find(i) == root]

	def roots(self):
		return [i for (i, x) in enumerate(self.parents) if x < 0]

	def group_count(self):
		return len(self.roots())

	def all_group_members(self):
		return {r: self.members(r) for r in self.roots()}

	def __str__(self):
		return '\n'.join(('{}: {}'.format(r, self.members(r)) for r in self.roots()))
init_min(P)
init_max(P)
uf = UnionFind(n - k + 1)
for i in range(n - k):
	m = query_min(i, i + k + 1)
	M = query_max(i, i + k + 1)
	if m == P[i] and M == P[i + k]:
		uf.unite(i, i + 1)
q = -1
s = 0
for i in range(k - 1):
	if P[i] < P[i + 1]:
		s += 1
if s == k - 1:
	q = 0
for i in range(n - k):
	s -= int(P[i] < P[i + 1])
	s += int(P[i + k - 1] < P[i + k])
	if s == k - 1:
		if q == -1:
			q = i + 1
		else:
			uf.unite(q, i + 1)
ans = uf.group_count()
print(ans)


import sys
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 7)
from collections import deque
(N, K, *P) = map(int, sys.stdin.read().split())
Kmin = []
deq = deque()
for i in range(K):
	while deq and P[deq[-1]] > P[i]:
		deq.pop()
	deq.append(i)
Kmin.append(deq[0])
for i in range(K, N):
	if deq[0] == i - K:
		deq.popleft()
	while deq and P[deq[-1]] > P[i]:
		deq.pop()
	deq.append(i)
	Kmin.append(deq[0])
Kmax = []
deq = deque()
for i in range(K):
	while deq and P[deq[-1]] < P[i]:
		deq.pop()
	deq.append(i)
Kmax.append(deq[0])
for i in range(K, N):
	if deq[0] == i - K:
		deq.popleft()
	while deq and P[deq[-1]] < P[i]:
		deq.pop()
	deq.append(i)
	Kmax.append(deq[0])
is_new_seq = [Kmin[i] != i or Kmax[i + 1] != i + K for i in range(N - K)]
is_new_seq
import itertools
incr = [1 if x < y else 0 for (x, y) in zip(P, P[1:])]
incr_cum = [0] + list(itertools.accumulate(incr))
is_stable = [y - x == K - 1 for (x, y) in zip(incr_cum, incr_cum[K - 1:])]
is_new_seq = [x & (not y) for (x, y) in zip(is_new_seq, is_stable[1:])]
answer = sum(is_new_seq)
if not is_stable[0]:
	answer += 1
	if any(is_stable):
		answer += 1
else:
	answer += 1
print(answer)


def init(seg, init_val, n, num):
	for i in range(n):
		seg[i + num - 1] = init_val[i]
	for i in range(num - 2, -1, -1):
		seg[i] = min(seg[2 * i + 1], seg[2 * i + 2])
	return seg

def query(seg, p, q, n, num):
	if q <= p:
		return float('inf')
	p += num - 1
	q += num - 2
	res = float('inf')
	while q - p > 1:
		if p & 1 == 0:
			res = min(res, seg[p])
		if q & 1 == 1:
			res = min(res, seg[q])
			q -= 1
		p = p // 2
		q = (q - 1) // 2
	if p == q:
		res = min(res, seg[p])
	else:
		res = min(min(res, seg[p]), seg[q])
	return res

def init2(seg, init_val, n, num):
	for i in range(n):
		seg[i + num - 1] = init_val[i]
	for i in range(num - 2, -1, -1):
		seg[i] = max(seg[2 * i + 1], seg[2 * i + 2])
	return seg

def query2(seg, p, q, n, num):
	ide_ele = -float('inf')
	if q <= p:
		return ide_ele
	p += num - 1
	q += num - 2
	res = ide_ele
	while q - p > 1:
		if p & 1 == 0:
			res = max(res, seg[p])
		if q & 1 == 1:
			res = max(res, seg[q])
			q -= 1
		p = p // 2
		q = (q - 1) // 2
	if p == q:
		res = max(res, seg[p])
	else:
		res = max(max(res, seg[p]), seg[q])
	return res

def main():
	import sys
	input = sys.stdin.readline
	(N, K) = map(int, input().split())
	P = list(map(int, input().split()))
	num = 2 ** (N - 1).bit_length()
	seg1 = [float('inf')] * 2 * num
	seg1 = init(seg1, P, N, num)
	seg2 = [-float('inf')] * 2 * num
	seg2 = init2(seg2, P, N, num)
	ans = 1
	c = 0
	tmp = 0
	for i in range(N - 1):
		if P[i] < P[i + 1]:
			tmp += 1
		else:
			if tmp >= K - 1:
				c += 1
			tmp = 0
	if tmp >= K - 1:
		c += 1
		tmp = 0
	for i in range(N - K):
		m = query(seg1, i, i + K + 1, N, num)
		M = query2(seg2, i, i + K + 1, N, num)
		if P[i] != m or P[i + K] != M:
			ans += 1
	print(ans - max(0, c - 1))
main()


from collections import deque
(N, K) = map(int, input().split())
P = list(map(int, input().split()))
upper = [1 for i in range(N)]
for i in range(1, N):
	x = N - i - 1
	if P[x] < P[x + 1]:
		upper[x] = upper[x + 1] + 1
skip = [-1, -1]
flg = False
for i in range(N):
	if upper[N - i - 1] >= K:
		skip.append(N - i - 1)
skip.pop()
deq_min = deque([P[0]])
deq_max = deque([P[0]])
minlen = 1
maxlen = 1
for i in range(1, K):
	while minlen > 0 and deq_min[-1] > P[i]:
		deq_min.pop()
		minlen -= 1
	deq_min.append(P[i])
	minlen += 1
	while maxlen > 0 and deq_max[-1] < P[i]:
		deq_max.pop()
		maxlen -= 1
	deq_max.append(P[i])
	maxlen += 1
ans = 1
next_skip = skip.pop()
for i in range(1, N - K + 1):
	new_i = i + K - 1
	min_rem = deq_min[0] == P[i - 1]
	max_add = deq_max[0] < P[new_i]
	if not (min_rem and max_add):
		if i != next_skip:
			ans += 1
	if i == next_skip:
		next_skip = skip.pop()
	if min_rem:
		deq_min.popleft()
		minlen -= 1
	if deq_max[0] == P[i - 1]:
		deq_max.popleft()
		maxlen -= 1
	while minlen > 0 and deq_min[-1] > P[new_i]:
		deq_min.pop()
		minlen -= 1
	deq_min.append(P[new_i])
	minlen += 1
	while maxlen > 0 and deq_max[-1] < P[new_i]:
		deq_max.pop()
		maxlen -= 1
	deq_max.append(P[new_i])
	maxlen += 1
print(ans)


from collections import defaultdict, deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random

def LI():
	return [int(x) for x in sys.stdin.readline().split()]

def I():
	return int(sys.stdin.readline())

def LS():
	return [list(x) for x in sys.stdin.readline().split()]

def S():
	res = list(sys.stdin.readline())
	if res[-1] == '\n':
		return res[:-1]
	return res

def IR(n):
	return [I() for i in range(n)]

def LIR(n):
	return [LI() for i in range(n)]

def SR(n):
	return [S() for i in range(n)]

def LSR(n):
	return [LS() for i in range(n)]
sys.setrecursionlimit(1000000)
mod = 1000000007

def A():
	(h, w, a, b) = LI()
	ans = [1] * a + [0] * (w - a)
	ans_ = [0] * a + [1] * (w - a)
	for i in range(h):
		if i < b:
			print(*ans, sep='')
		else:
			print(*ans_, sep='')
	return

def B():

	class SegmentTree:

		def __init__(self, size, default, op=min):
			self.size = 2 ** size.bit_length()
			self.dat = [default] * (self.size * 2)
			self.op = op

		def update(self, i, x):
			i += self.size
			self.dat[i] = x
			while i > 0:
				i >>= 1
				self.dat[i] = self.op(self.dat[i * 2], self.dat[i * 2 + 1])

		def add(self, i, x):
			i += self.size
			self.dat[i] = self.op(self.dat[i], x)
			while i > 0:
				i >>= 1
				self.dat[i] = self.op(self.dat[i], x)

		def get(self, a, b=None):
			if b is None:
				b = a + 1
			(l, r) = (a + self.size, b + self.size)
			res = None
			while l < r:
				if l & 1:
					if res is None:
						res = self.dat[l]
					else:
						res = self.op(res, self.dat[l])
					l += 1
				if r & 1:
					r -= 1
					if res is None:
						res = self.dat[r]
					else:
						res = self.op(res, self.dat[r])
				l >>= 1
				r >>= 1
			return res
	(n, k) = LI()
	p = LI()
	for i in range(n):
		p[i] += 1
	mi = SegmentTree(n, n, min)
	ma = SegmentTree(n, 0, max)
	for i in range(n):
		mi.update(i, p[i])
		ma.update(i, p[i])
	min_p = [mi.get(i, i + k) for i in range(n - k + 1)]
	max_p = [ma.get(i, i + k) for i in range(n - k + 1)]
	s = 1
	for i in range(k - 1):
		if p[i] < p[i + 1]:
			s += 1
		else:
			s = 1
	ans = 1
	a = s >= k
	f = 0
	for i in range(1, n - k + 1):
		if p[i + k - 2] < p[i + k - 1]:
			s += 1
		else:
			s = 1
		if s >= k:
			f |= 1
			continue
		elif min_p[i - 1] != p[i - 1] or max_p[i] != p[i + k - 1]:
			ans += 1
	if not a and f:
		ans += 1
	print(ans)
	return

def B_():
	(n, k) = LI()
	p = LI()
	for i in range(n - k + 1):
		print(i)
		s = p[i:i + k]
		s.sort()
		print(p[:i] + s + p[i + k:])

def C():
	return

def D():
	return

def E():
	return

def F():
	return
B()


from collections import deque
(N, K) = map(int, input().split())
P = list(map(int, input().split()))
disordered_count = [0]
for i in range(N - 1):
	if P[i] > P[i + 1]:
		disordered_count.append(disordered_count[i] + 1)
	else:
		disordered_count.append(disordered_count[i])
ordered = 0

def interval_min(a, K):
	q = deque()
	min_array = []
	for (i, v) in enumerate(a):
		while len(q) != 0 and a[q[len(q) - 1]] > v:
			q.pop()
		q.append(i)
		if i >= K - 1:
			min_array.append(q[0])
			if q[0] == len(min_array) - 1:
				q.popleft()
	return min_array

def interval_max(a, K):
	return interval_min([-i for i in a], K)
res = 0
min_array = interval_min(P, K)
max_array = interval_max(P, K)
for i in range(N - K + 1):
	if disordered_count[i] == disordered_count[i + K - 1]:
		ordered = 1
	elif i == 0:
		res += 1
	elif not (P[i - 1] == P[min_array[i - 1]] and P[i + K - 1] == P[max_array[i]]):
		res += 1
print(res + ordered)


INF = 10 ** 30

class Rmax:

	def __init__(self, size):
		self.n = 1
		while self.n < size:
			self.n *= 2
		self.node = [-INF] * (2 * self.n - 1)

	def Access(self, x):
		return self.node[x + self.n - 1]

	def Update(self, x, val):
		x += self.n - 1
		self.node[x] = val
		while x > 0:
			x = (x - 1) // 2
			self.node[x] = max(self.node[2 * x + 1], self.node[2 * x + 2])
		return

	def Get(self, l, r):
		(L, R) = (l + self.n, r + self.n)
		s = -INF
		while L < R:
			if R & 1:
				R -= 1
				s = max(s, self.node[R - 1])
			if L & 1:
				s = max(s, self.node[L - 1])
				L += 1
			L >>= 1
			R >>= 1
		return s

class Rmin:

	def __init__(self, size):
		self.n = 1
		while self.n < size:
			self.n *= 2
		self.node = [INF] * (2 * self.n - 1)

	def Access(self, x):
		return self.node[x + self.n - 1]

	def Update(self, x, val):
		x += self.n - 1
		self.node[x] = val
		while x > 0:
			x = (x - 1) // 2
			self.node[x] = min(self.node[2 * x + 1], self.node[2 * x + 2])
		return

	def Get(self, l, r):
		(L, R) = (l + self.n, r + self.n)
		s = INF
		while L < R:
			if R & 1:
				R -= 1
				s = min(s, self.node[R - 1])
			if L & 1:
				s = min(s, self.node[L - 1])
				L += 1
			L >>= 1
			R >>= 1
		return s
(n, k) = map(int, input().split())
p = list(map(int, input().split()))
(ma, mi) = (Rmax(n), Rmin(n))
for i in range(n):
	ma.Update(i, p[i])
	mi.Update(i, p[i])
ans = n - k + 1
same = set()
tmp = 0
for i in range(1, n):
	if p[i - 1] < p[i]:
		tmp += 1
	else:
		tmp = 0
	if tmp >= k - 1:
		same.add(i - k + 1)
ans -= max(0, len(same) - 1)
for i in range(k, n):
	if p[i - k] < mi.Get(i - k + 1, i) and ma.Get(i - k + 1, i) < p[i]:
		if not i - k in same and (not i - k + 1 in same):
			ans -= 1
print(ans)


class SWAG:

	def __init__(self, unit, f):
		self.fold_r = [unit]
		self.fold_l = [unit]
		self.data_r = []
		self.data_l = []
		self.f = f

	def __refill_right(self):
		temp = []
		n = len(self.data_l)
		for _ in range(n // 2):
			temp.append(self.popleft())
		for _ in range(n // 2, n):
			self.append(self.popleft())
		for t in temp[::-1]:
			self.appendleft(t)

	def __refill_left(self):
		temp = []
		n = len(self.data_r)
		for _ in range(n // 2):
			temp.append(self.pop())
		for _ in range(n // 2, n):
			self.appendleft(self.pop())
		for t in temp[::-1]:
			self.append(t)

	def append(self, x):
		self.fold_r.append(self.f(self.fold_r[-1], x))
		self.data_r.append(x)

	def appendleft(self, x):
		self.fold_l.append(self.f(self.fold_l[-1], x))
		self.data_l.append(x)

	def pop(self):
		if not self.data_r:
			self.__refill_right()
		self.fold_r.pop()
		return self.data_r.pop()

	def popleft(self):
		if not self.data_l:
			self.__refill_left()
		self.fold_l.pop()
		return self.data_l.pop()

	def fold_all(self):
		return self.f(self.fold_r[-1], self.fold_l[-1])
(n, k, *p) = map(int, open(0).read().split())
c = [0]
for (a, b) in zip(p, p[1:]):
	c += (c[-1] + (a < b),)
(*c, f) = [b - a == k - 1 for (a, b) in zip(c, c[k - 1:])]
x = not f
s_min = SWAG(10 ** 18, lambda a, b: a if a < b else b)
s_max = SWAG(0, lambda a, b: a if a > b else b)
(*_,) = map(s_min.append, p[:k - 1])
(*_,) = map(s_max.append, p[1:k])
for (i, (a, b, c)) in enumerate(zip(p, p[k:], c)):
	f |= c
	s_min.append(p[i + k - 1])
	s_max.append(b)
	if not c and (a != s_min.fold_all() or b != s_max.fold_all()):
		x += 1
	s_min.popleft()
	s_max.popleft()
print(x + f)