p02904 AtCoder Grand Contest 038 - Sorting a Segment
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
```python
n, k = map(int,input().split())
P = list(map(int,input().split()))

# for i in range(n-k+1):
#     pp = P[i:i+k]
#     pp.sort()
#     print(P[:i] + pp + P[i+k:])

A = []
B = []
VA = [0] * n
VB = [0] * n
import heapq
for i in range(k):
    heapq.heappush(A, P[i])  # 最小値用
    heapq.heappush(B, -P[i])  # 最大値用

ans = 1
for i in range(n-k):
    b = -heapq.heappop(B)
    while VB[b] == 1:
        b = -heapq.heappop(B)
    a = heapq.heappop(A)
    while VA[a] == 1:
        a = heapq.heappop(A)
    # print(i,a,b,A,B)
    # print(P[k+i] ,b ,P[i] , a)
    if not(P[k+i] > b and P[i] == a):
        ans += 1
        # print(i)
    heapq.heappush(A, a)
    heapq.heappush(B, -b) 
    heapq.heappush(A, P[k+i])
    heapq.heappush(B, -P[k+i])

    VA[P[i]] = 1
    VB[P[i]] = 1

# print("ans",ans)

AA = []
for i in range(n-1):
    if P[i+1] - P[i] >= 0:
        AA.append(1)
    else:
        AA.append(0)
s = sum(AA[:k-1])
t = 0
r = 0
if s == k-1:
    t += 1
    r = 1
for i in range(n-k):
    # print(AA)
    s += AA[k-1+i]
    s -= AA[i]
    if s == k-1:
        t += 1
        r += 1
    else:
        ans += max(0, r-1)
        r = 0
ans += max(0, r-1)
# print("t",t)
print(ans - max(0, t-1))
```