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

Now, he will perform the following operation exactly once:

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



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

Constraints

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

Input

Input is given from Standard Input in the following format:


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


Output

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

Examples

Input

5 3
0 2 1 4 3


Output

2


Input

4 4
0 1 2 3


Output

1


Input

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


Output

6

Solution (in PYTHON3):

Solution:
import sys
from collections import deque
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 = [] # min
    T = [] # max
    D = deque()
    C = 0 # swap count

    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

    # print(f"A: {A[0:K]}")
    # print(f"S: {S[0][0]}, T: {-T[0][0]}, C: {C}")
    # print(f"res: {res}, F: {F}")
    for i in range(N - K):
        # update swap
        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]
        
        # update T
        heapq.heappush(T, (-in_a, K + i))
        while T[0][1] <= i:
            heapq.heappop(T)

        if C == 0:
            F = True
        else:
            if not (T[0][0] == -in_a and S[0][0] == out_a):
                res += 1

        # print(f"in: {in_a}, out: {out_a}")
        # update S
        heapq.heappush(S, (in_a, K + i))
        while S[0][1] <= i:
            heapq.heappop(S)
        # print(f"S: {S[0][0]}, T: {-T[0][0]}, C: {C}")
        # if K + i + 1 < N:
       #      print(f"A: {A[i + 1:i+K+1]}")
        # print(f"res: {res}, F: {F}")
    if F:
        res += 1
    print(res)


if __name__ == "__main__":
    main()