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 SWAG():
    def __init__(self,unit,f):
        self.fold_r=[unit]
        self.fold_l=[unit]
        self.data_r=[]
        self.data_l=[]
        self.f=f
    def __refill_right(self):
        temp=[]
        n=len(self.data_l)
        for _ in range(n//2):
            temp.append(self.popleft())
        for _ in range(n//2,n):
            self.append(self.popleft())
        for _ in range(n//2):
            self.appendleft(temp.pop())
    def __refill_left(self):
        temp=[]
        n=len(self.data_r)
        for _ in range(n//2):
            temp.append(self.pop())
        for _ in range(n//2,n):
            self.appendleft(self.pop())
        for _ in range(n//2):
            self.append(temp.pop())
    def append(self,x):
        self.fold_r.append(self.f(self.fold_r[-1],x))
        self.data_r.append(x)
    def appendleft(self,x):
        self.fold_l.append(self.f(self.fold_l[-1],x))
        self.data_l.append(x)
    def pop(self):
        if not self.data_r:
            self.__refill_right()
        self.fold_r.pop()
        return self.data_r.pop()
    def popleft(self):
        if not self.data_l:
            self.__refill_left()
        self.fold_l.pop()
        return self.data_l.pop()
    def fold_all(self):
        return self.f(self.fold_r[-1],self.fold_l[-1])
n,k,*p=map(int,open(0).read().split())
c=[0]
for a,b in zip(p,p[1:]):c+=c[-1]+(a<b),
*c,f=[b-a==k-1for a,b in zip(c,c[k-1:])]
x=not f
s_min=SWAG(10**18,min)
s_max=SWAG(0,max)
*_,=map(s_min.append,p[:k-1])
*_,=map(s_max.append,p[1:k])
for i,(a,b,c)in enumerate(zip(p,p[k:],c)):
    f|=c
    s_min.append(p[i+k-1])
    s_max.append(b)
    if not c and(a!=s_min.fold_all()or b!=s_max.fold_all()):x+=1
    s_min.popleft()
    s_max.popleft()
print(x+f)