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:
import java.io.InputStream;
import java.io.PrintStream;
import java.util.*;

public class Main {

  public static void main(String[] args) {
    solve(System.in, System.out);
  }

  static void solve(InputStream is, PrintStream os) {
    Scanner sc = new Scanner(is);

    /* read */
    int n = sc.nextInt();
    int k = sc.nextInt();
    int[] a = new int[n];

    for (int i = 0; i < n; i++) {
      a[i] = sc.nextInt();
    }

    // find already k-length ordered segment
    Set<Integer> ordered = new HashSet<>();
//    int ordered = 0;
    int l = 0;
    int r = 1;
    for (l = 0; l < n; l++) {
      if (l == r) r++;
      while (r < n && a[r - 1] < a[r]) r++;
      if (k <= r - l) ordered.add(l);
    }

    SortedSet<Integer> set = new TreeSet<>();

    for (int i = 0; i < k; i++) {
      set.add(a[i]);
    }

    int res = n - k + 1;

    for (int i = 0; i < n - k; i++) {
      int min = set.first();
      int max = set.last();
      set.remove(a[i]);
      set.add(a[i + k]);
      if (min == a[i] && max < a[i + k] && !ordered.contains(i)) res--;
    }

    if (ordered.size() > 1) {
      res -= ordered.size() - 1;
    }
    os.println(res);

  }

}