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 CF1404C extends PrintWriter {
	CF1404C() { super(System.out); }
	static class Scanner {
		Scanner(InputStream in) { this.in = in; } InputStream in;
		byte[] bb = new byte[1 << 15]; int i, n;
		byte getc() {
			if (i == n) {
				i = n = 0;
				try { n = in.read(bb); } catch (IOException e) {}
			}
			return i < n ? bb[i++] : 0;
		}
		int nextInt() {
			byte c = 0; while (c <= ' ') c = getc();
			int a = 0; while (c > ' ') { a = a * 10 + c - '0'; c = getc(); }
			return a;
		}
	}
	Scanner sc = new Scanner(System.in);
	public static void main(String[] $) {
		CF1404C o = new CF1404C(); o.main(); o.flush();
	}

	int[] ft;
	void update(int i, int n) {
		while (i < n) {
			ft[i]++;
			i |= i + 1;
		}
	}
	int query(int i) {
		int sum = 0;
		while (i >= 0) {
			sum += ft[i];
			i &= i + 1; i--;
		}
		return sum;
	}
	void main() {
		int n = sc.nextInt();
		int q = sc.nextInt();
		int[] aa = new int[n];
		for (int i = 0; i < n; i++)
			aa[i] = i - (sc.nextInt() - 1);
		int[] ll = new int[q];
		int[] rr = new int[q];
		Integer[] hh = new Integer[q];
		int[] ans = new int[q];
		for (int h = 0; h < q; h++) {
			int x = sc.nextInt();
			int y = sc.nextInt();
			ll[h] = x;
			rr[h] = n - y;
			hh[h] = h;
		}
		Arrays.sort(hh, (h1, h2) -> rr[h1] - rr[h2]);
		ft = new int[n];
		for (int j = 0, k = 0, h_ = 0; h_ < q; h_++) {
			int h = hh[h_];
			while (j < rr[h]) {
				int a = aa[j];
				if (a == 0) {
					update(n - 1 - j, n);
					k++;
				} else if (a > 0 && k >= a) {
					int lower = 0, upper = j;
					while (upper - lower > 1) {
						int i = (lower + upper) / 2;
						if (query(n - 1 - i) >= a)
							lower = i;
						else
							upper = i;
					}
					update(n - 1 - lower, n);
					k++;
				}
				j++;
			}
			ans[h] = query(n - 1 - ll[h]);
		}
		for (int h = 0; h < q; h++)
			println(ans[h]);
	}
}
