Problem: Snuke has a permutation (P_0,P_1,\cdots,P_{N-1}) of (0,1,\cdots,N-1).

Now, he will perform the following operation exactly once:

* Choose K consecutive elements in P and sort them in ascending order.



Find the number of permutations that can be produced as P after the operation.

Constraints

* 2 \leq N \leq 200000
* 2 \leq K \leq N
* 0 \leq P_i \leq N-1
* P_0,P_1,\cdots,P_{N-1} are all different.
* All values in input are integers.

Input

Input is given from Standard Input in the following format:


N K
P_0 P_1 \cdots P_{N-1}


Output

Print the number of permutations that can be produced as P after the operation.

Examples

Input

5 3
0 2 1 4 3


Output

2


Input

4 4
0 1 2 3


Output

1


Input

10 4
2 0 1 3 7 5 4 6 8 9


Output

6

Solution (in PYTHON3):

Solution:
# -*- 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()