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 RangeMinimumQuery:
    def __init__(self, n, func=min, inf=float("inf")):
        self.n0 = 2**(n-1).bit_length()
        # 初期値
        self.op = func
        self.inf = inf
        self.data = [self.inf]*(2*self.n0-1)

    # [l, r)
    def query(self, l,r):
        l += self.n0
        r += self.n0
        res = self.inf
        while l < r:
            if r&1:
                r -= 1
                res = self.op(res, self.data[r-1])
            if l&1:
                res = self.op(res, self.data[l-1])
                l += 1
            l >>=1
            r >>=1
        return res

    def update(self, i, x):
        i += self.n0-1
        self.data[i] = x
        while i+1:
            i = ~-i//2
            self.data[i] = self.op(self.data[2*i+1], self.data[2*i+2])

n,k = map(int, input().split())
p = list(map(int, input().split()))

RminQ = RangeMinimumQuery(n)
RmaxQ = RangeMinimumQuery(n, func=max, inf=0)

for i, pi in enumerate(p):
    RminQ.update(i, pi)
    RmaxQ.update(i, pi)

a = [1]
for i in range(n-1):
    if p[i] < p[i+1]:
        a.append(a[-1]+1)
    else:
        a.append(1)

ans = n-k+1
flag = a[k-1] == k
for i in range(k, n):
    if (p[i] > RmaxQ.query(i-k+1, i) and p[i-k] < RminQ.query(i-k+1, i)) or (flag and a[i]>=k):
        ans -= 1
    if not flag and a[i] >= k:
        flag = True
print(ans)