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:
#!/usr/bin/env python3
#AGC38 B
#スライド最小値

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