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 JAVA):

Solution:
/*
If you want to aim high, aim high
Don't let that studying and grades consume you
Just live life young
******************************
If I'm the sun, you're the moon
Because when I go up, you go down
*******************************
I'm working for the day I will surpass you
https://www.a2oj.com/Ladder16.html
*/
import java.util.*;
import java.io.*;
import java.math.*;

   public class Main
   {
      public static void main(String omkar[]) throws Exception
      {
         BufferedReader infile = new BufferedReader(new InputStreamReader(System.in));  
         StringTokenizer st = new StringTokenizer(infile.readLine());
         int N = Integer.parseInt(st.nextToken());
         int K = Integer.parseInt(st.nextToken());
         int[] arr = new int[N];
         st = new StringTokenizer(infile.readLine());
         for(int i=0; i < N; i++)
            arr[i] = Integer.parseInt(st.nextToken());
         //dp[i] = longest increasing seq
         int res = 1;
         int[] dp = new int[N];
         dp[0] = 1;
         for(int i=1; i < N; i++)
         {
            if(arr[i] > arr[i-1])
               dp[i] = dp[i-1]+1;
            else
               dp[i] = 1;
         }
         TreeSet<Integer> curr = new TreeSet<Integer>();
         for(int i=0; i < K; i++)
            curr.add(arr[i]);
         boolean yeet = dp[K-1] >= K;
         if(yeet)
            res--;
         for(int i=1; i < N-K+1; i++)
         {
            int right = arr[K-1+i];
            int left = arr[i-1];
            if((curr.first() != left || curr.last() > right) && dp[K-1+i] < K)
               res++;
            else if(dp[K-1+i] >= K)
               yeet = true;
            curr.remove(left);
            curr.add(right);
         }
         if(yeet)
            res++;
         System.out.println(res);
      }
   }