Let a_1, …, a_n be an array of n positive integers. In one operation, you can choose an index i such that a_i = i, and remove a_i from the array (after the removal, the remaining parts are concatenated).

The weight of a is defined as the maximum number of elements you can remove.

You must answer q independent queries (x, y): after replacing the x first elements of a and the y last elements of a by n+1 (making them impossible to remove), what would be the weight of a?

Input

The first line contains two integers n and q (1 ≤ n, q ≤ 3 ⋅ 10^5) — the length of the array and the number of queries.

The second line contains n integers a_1, a_2, ..., a_n (1 ≤ a_i ≤ n) — elements of the array.

The i-th of the next q lines contains two integers x and y (x, y ≥ 0 and x+y < n).

Output

Print q lines, i-th line should contain a single integer — the answer to the i-th query.

Examples

Input


13 5
2 2 3 9 5 4 6 5 7 8 3 11 13
3 1
0 0
2 4
5 0
0 12


Output


5
11
6
1
0


Input


5 2
1 4 1 2 4
0 0
1 0


Output


2
0

Note

Explanation of the first query:

After making first x = 3 and last y = 1 elements impossible to remove, a becomes [×, ×, ×, 9, 5, 4, 6, 5, 7, 8, 3, 11, ×] (we represent 14 as × for clarity).

Here is a strategy that removes 5 elements (the element removed is colored in red):

  * [×, ×, ×, 9, \color{red}{5}, 4, 6, 5, 7, 8, 3, 11, ×] 
  * [×, ×, ×, 9, 4, 6, 5, 7, 8, 3, \color{red}{11}, ×] 
  * [×, ×, ×, 9, 4, \color{red}{6}, 5, 7, 8, 3, ×] 
  * [×, ×, ×, 9, 4, 5, 7, \color{red}{8}, 3, ×] 
  * [×, ×, ×, 9, 4, 5, \color{red}{7}, 3, ×] 
  * [×, ×, ×, 9, 4, 5, 3, ×] (final state) 



It is impossible to remove more than 5 elements, hence the weight is 5.
import java.io.*;
import java.util.*;

/*
polyakoff
*/

public class Main {

    static FastReader in;
    static PrintWriter out;
    static Random rand = new Random();
    static final int oo = (int) 2e9;
    static final long OO = (long) 4e18;
    static final int MOD = (int) 1e9 + 7;

    static int n, q;
    static int[] a;

    static class Treap {
        class Node {
            int x, y, cnt;
            Node left, right;

            Node(int x) {
                this.x = x;
                y = rand.nextInt();
                cnt = 1;
            }
        }
        Node root;

        int cnt(Node t) {
            return t == null ? 0 : t.cnt;
        }
        void pull(Node t) {
            t.cnt = 1 + cnt(t.left) + cnt(t.right);
        }
        Node merge(Node t1, Node t2) {
            if (t1 == null)
                return t2;
            if (t2 == null)
                return t1;
            if (t1.y >= t2.y) {
                t1.right = merge(t1.right, t2);
                pull(t1);
                return t1;
            } else {
                t2.left = merge(t1, t2.left);
                pull(t2);
                return t2;
            }
        }
        Node[] split(Node t, int k) {
            if (t == null)
                return new Node[]{null, null};
            if (t.x <= k) {
                Node[] tt = split(t.right, k);
                t.right = tt[0];
                pull(t);
                return new Node[]{t, tt[1]};
            } else {
                Node[] tt = split(t.left, k);
                t.left = tt[1];
                pull(t);
                return new Node[]{tt[0], t};
            }
        }
        Node insert(Node t, Node t2) {
            if (t == null)
                return t2;
            if (t2.y >= t.y) {
                Node[] tt = split(t, t2.x);
                t2.left = tt[0];
                t2.right = tt[1];
                pull(t2);
                return t2;
            }
            if (t2.x < t.x)
                t.left = insert(t.left, t2);
            else
                t.right = insert(t.right, t2);
            pull(t);
            return t;
        }
        Node erase(Node t, int x) {
            if (t.x == x)
                return merge(t.left, t.right);
            if (x < t.x)
                t.left = erase(t.left, x);
            else
                t.right = erase(t.right, x);
            pull(t);
            return t;
        }
        int kth(Node t, int k) {
            int ind = cnt(t.left) + 1;
            if (k == ind)
                return t.x;
            if (k < ind)
                return kth(t.left, k);
            else
                return kth(t.right, k - ind);
        }

        void insert(int x) {
            root = insert(root, new Node(x));
        }
        void erase(int x) {
            root = erase(root, x);
        }
        int kth(int k) {
            return kth(root, k);
        }
        int size() {
            return cnt(root);
        }
    }

    static class MergeTree {
        int t_size;
        int[][] t;

        void build(int v, int tl, int tr, int[] arr) {
            if (tl == tr) {
                t[v] = new int[1];
                t[v][0] = arr[tl];
                return;
            }
            int tm = (tl + tr) / 2;
            build(v * 2 + 1, tl, tm, arr);
            build(v * 2 + 2, tm + 1, tr, arr);
            t[v] = merge(t[v * 2 + 1], t[v * 2 + 2]);
        }

        int[] merge(int[] arr1, int[] arr2) {
            int[] res = new int[arr1.length + arr2.length];
            for (int i = 0, j = 0; i < arr1.length || j < arr2.length;) {
                if (j == arr2.length || (i < arr1.length && arr1[i] <= arr2[j]))
                    res[i + j] = arr1[i++];
                else
                    res[i + j] = arr2[j++];
            }
            return res;
        }

        int binSearch(int[] arr, int k) {
            int l = 0, r = arr.length;
            while (l < r) {
                int m = (l + r) / 2;
                if (arr[m] <= k)
                    l = m + 1;
                else
                    r = m;
            }
            return l;
        }
        int getOn(int v, int tl, int tr, int l, int r, int k) {
            if (r < tl || l > tr) return 0;
            if (l <= tl && tr <= r)
                return t[v].length - binSearch(t[v], k);
            int tm = (tl + tr) / 2;
            return getOn(v * 2 + 1, tl, tm, l, r, k) +
                    getOn(v * 2 + 2, tm + 1, tr, l, r, k);
        }

        void build(int[] arr) {
            t_size = arr.length;
            t = new int[t_size * 4][];
            build(0, 0, t_size - 1, arr);
        }
        int getOn(int l, int r, int k) {
            return getOn(0, 0, t_size - 1, l, r, k);
        }
    }

    static void solve() {
        n = in.nextInt();
        q = in.nextInt();

        a = new int[n];
        for (int i = 0; i < n; i++)
            a[i] = in.nextInt();

        Treap t = new Treap();

        int[] lol = new int[n]; Arrays.fill(lol, -1);
        for (int i = 0; i < n; i++) {
            int cur = i + 1 - a[i];
            if (cur >= 0 && cur <= t.size()) {
                if (cur == 0) {
                    lol[i] = i + 1;
                    t.insert(i + 1);
                } else {
                    int kth = t.kth(t.size() - cur + 1);
                    lol[i] = kth;
                    t.insert(kth);
                }
            }
        }
//        out.println(Arrays.toString(lol));

        MergeTree mt = new MergeTree();
        mt.build(lol);

        for (int qq = 0; qq < q; qq++) {
            int x = in.nextInt();
            int y = in.nextInt();
            out.println(mt.getOn(x, n - y - 1, x));
        }


    }

    public static void main(String[] args) throws FileNotFoundException {
        in = new FastReader(System.in);
//        in = new FastReader(new FileInputStream("sometext.txt"));
        out = new PrintWriter(System.out);
//        out = new PrintWriter(new FileOutputStream("output.txt"));

        int T = 1;
//        T = in.nextInt();
        while (T-- > 0)
            solve();

//        Thread thread = new Thread(null, () -> {
//            solve();
//        }, "Main", 1 << 28);
//        thread.start();
//        try {
//            thread.join();
//        } catch (InterruptedException e) {
//            e.printStackTrace();
//        }

//        out.flush();
        out.close();
    }

    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        FastReader(InputStream is) {
            br = new BufferedReader(new InputStreamReader(is));
        }

        Integer nextInt() {
            return Integer.parseInt(next());
        }

        Long nextLong() {
            return Long.parseLong(next());
        }

        Double nextDouble() {
            return Double.parseDouble(next());
        }

        String next() {
            while (st == null || !st.hasMoreTokens()) {
                st = new StringTokenizer(nextLine());
            }
            return st.nextToken();
        }

        String nextLine() {
            String s = "";
            try {
                s = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return s;
        }
    }

    static void dbg(Object... args) {
        for (Object arg : args)
            out.print(" " + arg);
        out.flush();
    }

}