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 heapq import *
input = sys.stdin.readline


def solve(n, k, p):
    res = n-k+1
    count = 0
    length = 1
    
    judge_max = [-x for x in p[:k]]
    judge_min = p[:k]
    heapify(judge_max)
    heapify(judge_min)
    already = [False]*n
    
    for i in range(k-1):
        if p[i] < p[i+1]:
            length += 1
        else:
            length = 1
            
    if length == k:
        count += 1
    
    for i in range(k-1, n-1):
        if p[i] < p[i+1]:
            length += 1
        else:
            length = 1
        
        already[p[i-k+1]] = True
        while True:
            vmax = -judge_max[0]
            if already[vmax]:
                heappop(judge_max)
                continue
            else:
                break
        while True:
            vmin = judge_min[0]
            if already[vmin]:
                heappop(judge_min)
                continue
            else:
                break
        if p[i-k+1] < vmin and vmax < p[i+1]:
            res -= 1
        
        elif length >= k:
            if count:
                res -= 1
            count += 1
        heappush(judge_max, -p[i+1])
        heappush(judge_min, p[i+1])
    
    return res

    
def main():
    n, k = map(int, input().split())
    p = list(map(int, input().split()))
    
    ans = solve(n, k, p)
    print(ans)


if __name__ == "__main__":
    main()