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.
/**
 * author: derrick20
 * created: 9/9/20 5:04 PM
 */
import java.io.*;
import java.util.*;

public class FixedPointRemoval implements Runnable {
    public static void main(String[] args) throws Exception {
        new Thread(null, new FixedPointRemoval(), ": )", 1 << 28).start();
    }

    public void run() {
        FastScanner sc = new FastScanner();
        PrintWriter out = new PrintWriter(System.out);

        int N = sc.nextInt();
        int Q = sc.nextInt();
        int[] d = new int[N + 1];
        for (int i = 1; i <= N; i++) {
            d[i] = i - sc.nextInt();
        }
        int[][] queries = new int[Q][3];
        int[] answers = new int[Q];
        // range = [x + 1, N - y], 1-indexed
        Arrays.setAll(queries, i -> new int[]{sc.nextInt() + 1, N - sc.nextInt(), i});
        Arrays.sort(queries, Comparator.comparingInt(pair -> pair[1]));
        int ptr = 0;
        BIT bit = new BIT(N);
//        System.out.println(Arrays.toString(d));
        for (int r = 1; r <= N; r++) {
            if (d[r] >= 0 && bit.sum(1) >= d[r]) {
                // need to find last position which has enough 0's
                int rightMost = bit.search(r, d[r]);
                bit.add(1, 1);
                bit.add(rightMost + 1, -1);
//                System.out.println("added 1 up to " + rightMost);
//                System.out.println(bit);
            }
            while (ptr < Q && queries[ptr][1] == r) {
                int id = queries[ptr][2];
                int l = queries[ptr][0];
                answers[id] = bit.sum(l);
                ptr++;
            }
        }
        for (int ans : answers) {
            out.println(ans);
        }
        out.close();
    }

    static class BIT {
        int[] tree;
        public BIT(int max) {
            tree = new int[max + 1];
        }

        public String toString() {
            StringBuilder sb = new StringBuilder();
            for (int i = 1; i < tree.length; i++) {
                sb.append(sum(i)).append(" ");
            }
            return sb.toString();
        }

        public int search(int hi, int val) {
            int pos = 0; // minimum if nothing possible. It must be possible
            int amt = 0;
            for (int bit = Integer.highestOneBit(hi); bit >= 1; bit >>= 1) {
                if (pos + bit <= hi && val <= amt + tree[pos + bit]) {
                    amt += tree[pos + bit];
                    pos += bit;
                }
            }
            return pos;
        }

        public void add(int i, int v) {
            while (i < tree.length) {
                tree[i] += v;
                i += i & -i;
            }
        }

        public int sum(int i) {
            int ans = 0;
            while (i > 0) {
                ans += tree[i];
                i -= i & -i;
            }
            return ans;
        }
    }

    static class FastScanner {
        private int BS = 1 << 16;
        private char NC = (char) 0;
        private byte[] buf = new byte[BS];
        private int bId = 0, size = 0;
        private char c = NC;
        private double cnt = 1;
        private BufferedInputStream in;

        public FastScanner() {
            in = new BufferedInputStream(System.in, BS);
        }

        public FastScanner(String s) {
            try {
                in = new BufferedInputStream(new FileInputStream(new File(s)), BS);
            } catch (Exception e) {
                in = new BufferedInputStream(System.in, BS);
            }
        }

        private char getChar() {
            while (bId == size) {
                try {
                    size = in.read(buf);
                } catch (Exception e) {
                    return NC;
                }
                if (size == -1) return NC;
                bId = 0;
            }
            return (char) buf[bId++];
        }

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

        public int[] nextInts(int N) {
            int[] res = new int[N];
            for (int i = 0; i < N; i++) {
                res[i] = (int) nextLong();
            }
            return res;
        }

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

        public long nextLong() {
            cnt = 1;
            boolean neg = false;
            if (c == NC) c = getChar();
            for (; (c < '0' || c > '9'); c = getChar()) {
                if (c == '-') neg = true;
            }
            long res = 0;
            for (; c >= '0' && c <= '9'; c = getChar()) {
                res = (res << 3) + (res << 1) + c - '0';
                cnt *= 10;
            }
            return neg ? -res : res;
        }

        public double nextDouble() {
            double cur = nextLong();
            return c != '.' ? cur : cur + nextLong() / cnt;
        }

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

        public String next() {
            StringBuilder res = new StringBuilder();
            while (c <= 32) c = getChar();
            while (c > 32) {
                res.append(c);
                c = getChar();
            }
            return res.toString();
        }

        public String nextLine() {
            StringBuilder res = new StringBuilder();
            while (c <= 32) c = getChar();
            while (c != '\n') {
                res.append(c);
                c = getChar();
            }
            return res.toString();
        }

        public boolean hasNext() {
            if (c > 32) return true;
            while (true) {
                c = getChar();
                if (c == NC) return false;
                else if (c > 32) return true;
            }
        }
    }
    static void ASSERT(boolean assertion, String message) {
        if (!assertion) throw new AssertionError(message);
    }
    static void ASSERT(boolean assertion) {
        if (!assertion) throw new AssertionError();
    }
}