# -*- coding: utf-8 -*-
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)
# local only
# if not __debug__:
#     fin = open('in_1.txt', 'r')
#     sys.stdin = fin
# local only
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()
# template

class SparseTable():
    """SparseTable:2の冪乗ごとにテーブルを作成しておいて，min,maxなどを高速に行う。セグ木から更新を除いたもの。"""
    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]

# BEGIN CUT HERE
class UnionFind():
    '''
    UnionFind木

    Parameters
    --------
        n (int): UnionFind木のサイズ

    Methods
    --------
        unite(x: int, y: int) -> None
            ノード x とノード y を結合する
        same(x: int, y: int) -> bool
            ノード x とノード y が同じ集合に属するか判定する
        size(x: int) -> int
            ノード x を含む集合の要素数を返す

    '''

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

    def unite(self, x: int, y: int) -> bool:
        '''x と y を結合'''
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return False  # 元々結合されている場合はFalseを返し終了する
        elif self._data[x] > self._data[y]:
            x, y = y, x  # swap
        self._data[x] += self._data[y]
        self._data[y] = x
        return True

    def root(self, x: int) -> int:
        '''ノード x の親を返す'''
        while self._data[x] >= 0:
            x = self._data[x]
        return x

    def same(self, x: int, y: int) -> bool:
        '''x と y が同じグループに属するか判定'''
        return self.root(x) == self.root(y)

    def size(self, x: int) -> int:
        '''x を含むグループのノード数を返す'''
        return -self._data[self.root(x)]
# END CUT HERE


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()
    # ba = bruteforce(N, K, P)
    def func(x: tuple, y: tuple):
        return (max(x[0], y[0]), min(x[1], y[1]))
    spt = SparseTable(N, func, (int(-1e9), int(1e9)))
    for i, val in enumerate(P):
        spt.set(i, val)
    spt.build()
    uf = UnionFind(N - K + 1)
    # しゃくとり法
    right = 1  # [0, 1) は確実に条件を満たす
    left = 0
    ans = 0
    s = []
    while left < N - K + 1:
        # right を 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


if __name__ == '__main__':
    # generate_testcase()
    # import cProfile
    # cProfile.run('main()')
    main()


Measured memory_bytes: 158548