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:
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
        else:
            if t2 > st2.querymin(i,i+K-1):
                ans += 1

if mono_increased == True:
    print(ans+1)
else:
    print(ans)