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.*;
import java.util.*;

@SuppressWarnings("unused")
public class Main {
    private FastScanner in = new FastScanner(System.in);
    private PrintWriter out = new PrintWriter(System.out);
    final int MOD = (int)1e9+7;
    long ceil(long a, long b){return (a + b - 1) / b;}

    void solve() throws Exception{
        int N = in.nextInt(), K = in.nextInt();
        int[] P = in.nextIntArray(N);

        MultiSet<Integer> set = new MultiSet<>();
        for(int i = 0; i < K; i++) set.add(P[i]);
        UnionFind uf = new UnionFind(N-K+1);

        int min = -1, max = -1;
        for(int i = 1; i + K <= N; i++){
            min = set.first();
            set.remove(P[i-1]);
            set.add(P[i+K-1]);
            max = set.last();
            //out.println(min + " " + max + " " + P[i-1] + " " + P[i+K-1]);
            if(min == P[i-1] && max == P[i+K-1]){
                uf.union(i-1, i);
            }
        }

        int[] acc = new int[N];
        for(int i = 1; i < N; i++){
            acc[i] = acc[i-1] + (P[i] < P[i-1] ? 1  : 0);
        }
        int idx = -1;
        for(int i = 0; i + K <= N; i++){
            int num = acc[i+K-1] - acc[i];
            //out.println(num);
            if(num == 0){
                if(idx != -1) uf.union(i, idx);
                idx = i;
            }
        }

        out.println(uf.group);
    }

    class MultiSet<T extends Comparable<T>>{
        TreeMap<T, Integer> map = new TreeMap<>();
        int num = 0;

        public int add(T e){
            map.put(e, map.getOrDefault(e, 0) + 1);
            num++;
            return map.get(e);
        }

        public int add(T e, int n){
            map.put(e, map.getOrDefault(e, 0) + n);
            num += n;
            return map.get(e);
        }

        //要素eが集合に含まれない<=>mapにeのマッピングは存在しない
        public boolean remove(T e){
            if(!map.containsKey(e)) return false;
            int c = map.get(e);
            if(c == 1) map.remove(e);
            else map.put(e, c - 1);
            num--;
            return true;
        }

        public boolean remove(T e, int n){
            if(map.getOrDefault(e, 0) < n) return false;
            int c = map.get(e);
            if(c == n) map.remove(e);
            else map.put(e, c - n);
            num -= n;
            return true;
        }

        public boolean delete(T e){
            if(!map.containsKey(e)) return false;
            num -= map.get(e);
            map.remove(e);
            return true;
        }

        public int count(T e){return map.getOrDefault(e, 0);}
        public int size(){return num;}//map.size()ではなく、集合に追加された要素数を返す
        public boolean isEmpty(){return map.isEmpty();}
        public boolean contains(T e){return map.containsKey(e);}

        public T lower(T e){return map.lowerKey(e);}                    //max(<e)
        public T higher(T e){return map.higherKey(e);}                  //min(e<)
        public T floor(T e){return map.floorKey(e);}                    //max(<=e)
        public T ceiling(T e){return map.ceilingKey(e);}                //min(e<=)
        public T first(){return this.isEmpty() ? null : map.firstKey();}//min
        public T last(){return this.isEmpty() ? null : map.lastKey();}  //max
    }

    class UnionFind{
        int[] par;
        int[] rank;
        int[] size;
        int group;

        UnionFind(int n){
            par = new int[n];
            rank = new int[n];
            size = new int[n];
            group = n;
            for(int i = 0; i < n; i++){
                par[i] = i;
                rank[i] = 0;
                size[i] = 1;
            }
        }

        //経路圧縮しながらrootを求める
        int find(int x){
            if(par[x] == x){
                return x;
            }else{
                int f = find(par[x]);
                return par[x] = f;
            }
        }

        //ランクの小さいほうにつなげる
        boolean union(int x, int y){
            x = find(x);
            y = find(y);
            if(x == y) return false;

            if(rank[x] < rank[y]){
                int tmp = x; x = y; y = tmp;
            }

            //y(のroot)をx(のroot)の下にくっつける
            //yのほうが重くなる(ポテンシャルが高くなる)
            if(rank[x] == rank[y]) rank[x]++;
            group--;
            par[y] = x;
            size[x] += size[y];

            return true;
        }

        boolean isSame(int x, int y){
            return find(x) == find(y);
        }
    }

    //end solve

    public static void main(String[] args) throws Exception {
        new Main().m();
    }

    private void m() throws Exception {
        solve();
        out.flush();
    }

    static class FastScanner {
        Reader input;

        FastScanner() {this(System.in);}
        FastScanner(InputStream stream) {this.input = new BufferedReader(new InputStreamReader(stream));}

        int nextInt() {return (int) nextLong();}

        long nextLong() {
            try {
                int sign = 1;
                int b = input.read();
                while ((b < '0' || '9' < b) && b != '-' && b != '+') {
                    b = input.read();
                }
                if (b == '-') {
                    sign = -1;
                    b = input.read();
                } else if (b == '+') {
                    b = input.read();
                }
                long ret = b - '0';
                while (true) {
                    b = input.read();
                    if (b < '0' || '9' < b) return ret * sign;
                    ret *= 10;
                    ret += b - '0';
                }
            } catch (IOException e) {
                e.printStackTrace();
                return -1;
            }
        }

        double nextDouble() {
            try {
                double sign = 1;
                int b = input.read();
                while ((b < '0' || '9' < b) && b != '-' && b != '+') {
                    b = input.read();
                }
                if (b == '-') {
                    sign = -1;
                    b = input.read();
                } else if (b == '+') {
                    b = input.read();
                }
                double ret = b - '0';
                while (true) {
                    b = input.read();
                    if (b < '0' || '9' < b) break;
                    ret *= 10;
                    ret += b - '0';
                }
                if (b != '.') return sign * ret;
                double div = 1;
                b = input.read();
                while ('0' <= b && b <= '9') {
                    ret *= 10;
                    ret += b - '0';
                    div *= 10;
                    b = input.read();
                }
                return sign * ret / div;
            } catch (IOException e) {
                e.printStackTrace();
                return Double.NaN;
            }
        }

        char nextChar() {
            try {
                int b = input.read();
                while (Character.isWhitespace(b)) {
                    b = input.read();
                }
                return (char) b;
            } catch (IOException e) {
                e.printStackTrace();
                return 0;
            }
        }

        String nextStr() {
            try {
                StringBuilder sb = new StringBuilder();
                int b = input.read();
                while (Character.isWhitespace(b)) {
                    b = input.read();
                }
                while (b != -1 && !Character.isWhitespace(b)) {
                    sb.append((char) b);
                    b = input.read();
                }
                return sb.toString();
            } catch (IOException e) {
                e.printStackTrace();
                return "";
            }
        }

        public int[] nextIntArray(int n) {
            int[] res = new int[n];
            for (int i = 0; i < n; i++) {
                res[i] = nextInt();
            }
            return res;
        }

        public int[] nextIntArrayDec(int n) {
            int[] res = new int[n];
            for (int i = 0; i < n; i++) {
                res[i] = nextInt() - 1;
            }
            return res;
        }

        public int[] nextIntArray1Index(int n) {
            int[] res = new int[n + 1];
            for (int i = 0; i < n; i++) {
                res[i + 1] = nextInt();
            }
            return res;
        }

        public long[] nextLongArray(int n) {
            long[] res = new long[n];
            for (int i = 0; i < n; i++) {
                res[i] = nextLong();
            }
            return res;
        }

        public long[] nextLongArrayDec(int n) {
            long[] res = new long[n];
            for (int i = 0; i < n; i++) {
                res[i] = nextLong() - 1;
            }
            return res;
        }

        public long[] nextLongArray1Index(int n) {
            long[] res = new long[n + 1];
            for (int i = 0; i < n; i++) {
                res[i + 1] = nextLong();
            }
            return res;
        }

        public double[] nextDoubleArray(int n) {
            double[] res = new double[n];
            for (int i = 0; i < n; i++) {
                res[i] = nextDouble();
            }
            return res;
        }

        public Long[] nextWrapperLongArray(int n) {
            Long[] res = new Long[n];
            for (int i = 0; i < n; i++) {
                res[i] = nextLong();
            }
            return res;
        }

        public Long[] nextWrapperLongArrayDec(int n) {
            Long[] res = new Long[n];
            for (int i = 0; i < n; i++) {
                res[i] = nextLong() - 1;
            }
            return res;
        }

        public Long[] nextWrapperLongArray1Index(int n) {
            Long[] res = new Long[n + 1];
            for (int i = 0; i < n; i++) {
                res[i + 1] = nextLong();
            }
            return res;
        }
    }
}