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.*;
 
public class Main {
    static final long MOD = 1000000007L;
    static final int INF = 50000000;
    static final int NINF = -50000000;
    public static void main(String[] args) {
        FastScanner sc = new FastScanner();
        PrintWriter pw = new PrintWriter(System.out);
        
        int N = sc.ni();
        int Q = sc.ni();
        int[] nums = new int[N];
        for (int i = 0; i < N; i++)
        	nums[i] = (i+1)-sc.ni();
        int[][] queries = new int[Q][3];
        for (int q = 0; q < Q; q++) {
        	queries[q][0] = sc.ni();
        	queries[q][1] = N-1-sc.ni();
        	queries[q][2] = q;
        }
        queries = sort(queries);
        //pw.println(Arrays.toString(nums));
        //pw.println(Arrays.deepToString(queries));
        int q = 0;
        
        BinaryIndexedTree bit = new BinaryIndexedTree(N);
        int[] ans = new int[Q];
        for (int i = 0; i < N; i++) {
        	if (nums[i] >= 0 && bit.sum(0,i) >= nums[i]) {
        		int low = 0;
        		int high = i;
        		while (low < high) {
        			int med = (low+high+1)/2;
        			if (bit.sum(med,i) >= nums[i]) {
        				low = med;
        			} else {
        				high = med-1;
        			}
        		}
        		bit.add(1, low);
        	}
        	while (q < Q && queries[q][1]==i) {
        		ans[queries[q][2]] = bit.sum(queries[q][0],i);
        		q++;
        	}
        }
        
        for (int a: ans)
        	pw.println(a);
        pw.close();
    }
    
    public static int[][] sort(int[][] arr) {
    	//Sort an array (immune to quicksort TLE)
    	Random rgen = new Random();
    	for (int i = 0; i < arr.length; i++) {
    		int randomPosition = rgen.nextInt(arr.length);
    		int[] temp = arr[i];
    		arr[i] = arr[randomPosition];
    		arr[randomPosition] = temp;
    	}
    	Arrays.sort(arr, new Comparator<int[]>() {
    		@Override
    		public int compare(int[] arr1, int[] arr2) {
    			return arr1[1]-arr2[1];
    			//Ascending order.
    		}
    	});
    	return arr;
    }
    
    //0 indexed
    static class BinaryIndexedTree {
    	public int[] arr;

    	public BinaryIndexedTree (int N) {
    		arr = new int[N+1];
    	}

    	//add k to the i-th element.
    	public void add(int k, int i) {
    		int node = i+1;
    		while (node < arr.length) {
    			arr[node] += k;
    			node += node & (-node);
    		}
    	}

    	//sum up the elements from input[s_i] to input[e_i], from [s_i,e_i].
    	public int sum(int s_i, int e_i) {
    		return sum(e_i+1) - sum(s_i);
    	}

    	private int sum(int i) {
    		int total = 0;
    		int node = i;
    		while (node > 0) {
    			total += arr[node];
    			node -= node & (-node);
    		}
    		return total;
    	}
    }
 
    static class FastScanner {
        BufferedReader br;
        StringTokenizer st;
 
        public FastScanner() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }
 
        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
 
        int ni() {
            return Integer.parseInt(next());
        }
 
        long nl() {
            return Long.parseLong(next());
        }
 
        double nd() {
            return Double.parseDouble(next());
        }
 
        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
}