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

public class Main {
    public static void main(String args[]) {new Main().run();}

    FastReader in = new FastReader();
    PrintWriter out = new PrintWriter(System.out);
    void run(){
        work();
        out.flush();
    }
    long mod=998244353;
    long gcd(long a,long b) {
        return a==0?b:gcd(b%a,a);
    }
    final long inf=Long.MAX_VALUE/3;
    int[] S;
    int[] S2;
    void work(){
        int n=ni(),q=ni();
        int[] A=new int[n+1];
        for(int i=1;i<=n;i++){
            A[i]=ni();
        }
        S=new int[n+1];
        S2=new int[n+1];
        int[] pre=new int[n+1];
        for(int i=1;i<=n;i++){
            if(A[i]==i){
                pre[i]=i;
                add(i,S2);
            }else if(i>A[i]){
                int l=0,r=i;
                while(l<r){
                    int m=(l+r)/2;
                    int query = query(Math.max(m, 1), i, S2);
                    if(query>=i-A[i]){
                        l=m+1;
                    }else{
                        r=m;
                    }
                }
                if(l>1){
                    add(l-1,S2);
                    pre[i]=l-1;
                }
            }
        }
        ArrayList<int[]> list=new ArrayList<>();
        for(int i=1;i<=n;i++){
            if(pre[i]!=0){
                list.add(new int[]{pre[i],i});
            }
        }
        Collections.sort(list,(a1,a2)->a1[1]-a2[1]);
        int[][] B=new int[q][];
        for(int i=0;i<q;i++){
            B[i]=new int[]{ni()+1,n-ni(),i};
        }
        int[] ret=new int[q];
        Arrays.sort(B,(a1,a2)->a1[1]-a2[1]);
        for(int i=0,j=0;i<q;i++){
            while(j<list.size()&&list.get(j)[1]<=B[i][1]){
                add(list.get(j)[0],S);
                j++;
            }
            int idx=B[i][2];
            ret[idx]=query(B[i][0],B[i][1],S);
        }
        for(int r:ret){
            out.println(r);
        }
    }

    int lowbit(int f){
        return f&-f;
    }

    void add(int idx,int[] S){
        for(;idx<S.length;idx+=lowbit(idx)){
            S[idx]++;
        }
    }

    int query(int s,int e,int[] S){
        return query(e,S)-query(s-1,S);
    }
    int query(int idx,int[] S){
        int ret=0;
        for(;idx>0;idx-=lowbit(idx)){
            ret+=S[idx];
        }
        return ret;
    }

    //input
    @SuppressWarnings("unused")
    private ArrayList<Integer>[] ng(int n, int m) {
        ArrayList<Integer>[] graph=(ArrayList<Integer>[])new ArrayList[n];
        for(int i=0;i<n;i++) {
            graph[i]=new ArrayList<>();
        }
        for(int i=1;i<=m;i++) {
            int s=in.nextInt()-1,e=in.nextInt()-1;
            graph[s].add(e);
            graph[e].add(s);
        }
        return graph;
    }

    private ArrayList<long[]>[] ngw(int n, int m) {
        ArrayList<long[]>[] graph=(ArrayList<long[]>[])new ArrayList[n];
        for(int i=0;i<n;i++) {
            graph[i]=new ArrayList<>();
        }
        for(int i=1;i<=m;i++) {
            long s=in.nextLong()-1,e=in.nextLong()-1,w=in.nextLong();
            graph[(int)s].add(new long[] {e,w});
            graph[(int)e].add(new long[] {s,w});
        }
        return graph;
    }

    private int ni() {
        return in.nextInt();
    }

    private long nl() {
        return in.nextLong();
    }

    private String ns() {
        return in.next();
    }

    private long[] na(int n) {
        long[] A=new long[n];
        for(int i=0;i<n;i++) {
            A[i]=in.nextLong();
        }
        return A;
    }
    private int[] nia(int n) {
        int[] A=new int[n];
        for(int i=0;i<n;i++) {
            A[i]=in.nextInt();
        }
        return A;
    }
}

class FastReader
{
    BufferedReader br;
    StringTokenizer st;

    public FastReader()
    {
        br=new BufferedReader(new InputStreamReader(System.in));
    }


    public String next()
    {
        while(st==null || !st.hasMoreElements())//回车，空行情况
        {
            try {
                st = new StringTokenizer(br.readLine());
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
        return st.nextToken();
    }

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

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