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.*;
import java.lang.reflect.Array;
import java.math.BigInteger;

public class tr0 {
	static PrintWriter out;
	static StringBuilder sb;
	static int mod = 1000000007;
	static long inf = (long) 1e14;
	static int n, a, b, da, db;
	static ArrayList<Integer>[] ad;
	static int[][] memo;
	static boolean f;
	static boolean vis[];
	static int[] sub;

	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		out = new PrintWriter(System.out);
		n = sc.nextInt();
		int q = sc.nextInt();
		int[] a = new int[n];
		int z = 0;
		int[] ans = new int[n];
		int total = 0;
		int N = 1;
		while (N < n)
			N <<= 1;
		int[] arr = new int[N + 1];
		Arrays.fill(arr, 1000000);
		for (int i = 0; i < n; i++) {
			a[i] = sc.nextInt() - i - 1;
			if (a[i] > 0)
				a[i] = -1000000000;
			if (a[i] * -1 <= z) {
				z++;
				ans[i] = 1;
				if (a[i] == 0)
					arr[i + 1] = 1000000;
				else
					arr[i + 1] = a[i] + z - 1;
			}

		}
		FenwickTree prx = new FenwickTree(n);
		int[] dp = new int[n];
		Arrays.fill(arr, 1000000);
		for (int i = 0; i < n; i++) {
			if (a[i] == 0) {
				prx.point_update(i + 1, 1);
				dp[i] = i;
				arr[i + 1] = i;
				continue;
			}
			int id = 1000000;
			int lo = 0;
			int hi = i - 1;
			while (lo <= hi) {
				int mid = (lo + hi) >> 1;
				int vx = prx.rsq(mid + 1);
				if (vx + a[i] >= 0) {
					id = mid;
					lo = mid + 1;
				} else
					hi = mid - 1;
			}
			dp[i] = id;
			arr[i + 1] = id;
			if (id != 1000000)
				prx.point_update(id + 1, 1);
		}
//System.out.println(Arrays.toString(dp));
		total = z;
		int[] pre = new int[n];
		int[] suff = new int[n];
		pre[0] = ans[0];
		suff[n - 1] = ans[n - 1];
		for (int i = 1; i < n; i++)
			pre[i] += pre[i - 1] + ans[i];
		for (int i = n - 2; i >= 0; i--)
			suff[i] = suff[i + 1] + ans[i];
		SegmentTree st = new SegmentTree(arr);
		while (q-- > 0) {
			int x = sc.nextInt();
			int y = sc.nextInt();
			int print = total;
			if (y != 0) {
				print -= suff[n - y];
			}
			if (x != 0) {
				print -= pre[x - 1];
				if (x + 1 <= n - y)
					print -= st.query(x + 1, n - y, x);
			}
			out.println(print);
		}
		out.close();
	}

	public static class FenwickTree { // one-based DS

		int n;
		int[] ft;

		FenwickTree(int size) {
			n = size;
			ft = new int[n + 1];
		}

		int rsq(int b) // O(log n)
		{
			int sum = 0;
			while (b <= n) {
				sum += ft[b];
				b += b & -b;
			} // min?
			return sum;
		}

		void point_update(int k, int val) // O(log n), update = increment
		{
			while (k > 0) {
				ft[k] += val;
				k -= k & -k;
			} // min?
		}

	}

	public static class SegmentTree { // 1-based DS, OOP

		int N; // the number of elements in the array as a power of 2 (i.e. after padding)
		int[] array;
		int[][] sTree;

		SegmentTree(int[] in) {
			array = in;
			N = in.length - 1;
			sTree = new int[N << 1][]; // no. of nodes = 2*N - 1, we add one to cross out index zero
			build(1, 1, N);
		}

		void build(int node, int b, int e) // O(n)
		{
			if (b == e)
				sTree[node] = new int[] { array[b] };
			else {
				int mid = b + e >> 1;
				build(node << 1, b, mid);
				build(node << 1 | 1, mid + 1, e);
				sTree[node] = new int[sTree[node << 1].length + sTree[node << 1 | 1].length];
				int l = 0;
				int r = 0;
				for (int i = 0; i < sTree[node].length; i++) {
					if (sTree[node << 1].length == l) {
						sTree[node][i] = sTree[node << 1 | 1][r];
						r++;
					} else if (sTree[node << 1 | 1].length == r) {
						sTree[node][i] = sTree[node << 1][l];
						l++;
					} else if (sTree[node << 1][l] < sTree[node << 1 | 1][r]) {
						sTree[node][i] = sTree[node << 1][l];
						l++;
					} else {
						sTree[node][i] = sTree[node << 1 | 1][r];
						r++;
					}
				}
			}
		}

		int query(int i, int j, int val) {
			return query(1, 1, N, i, j, val);
		}

		int query(int node, int b, int e, int i, int j, int val) // O(log n)
		{
			if (i > e || j < b)
				return 0;
			if (b >= i && e <= j) {
				int id = -1;
				int lo = 0;
				int hi = sTree[node].length - 1;
				// System.out.println(Arrays.toString(sTree[node]));
				while (lo <= hi) {
					int mid = lo + hi >> 1;
					if (sTree[node][mid] < val) {
						id = mid;
						lo = mid + 1;
					} else {
						hi = mid - 1;
					}
				}
				return id + 1;
//				if (id == -1)
//					return 0;
//				return sTree[node].length - (id);
			}
			int mid = b + e >> 1;
			int q1 = query(node << 1, b, mid, i, j, val);
			int q2 = query(node << 1 | 1, mid + 1, e, i, j, val);
			return q1 + q2;
		}
	}

	static class Scanner {
		StringTokenizer st;
		BufferedReader br;

		public Scanner(InputStream system) {
			br = new BufferedReader(new InputStreamReader(system));
		}

		public Scanner(String file) throws Exception {
			br = new BufferedReader(new FileReader(file));
		}

		public String next() throws IOException {
			while (st == null || !st.hasMoreTokens())
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}

		public String nextLine() throws IOException {
			return br.readLine();
		}

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

		public double nextDouble() throws IOException {
			return Double.parseDouble(next());
		}

		public char nextChar() throws IOException {
			return next().charAt(0);
		}

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

		public int[] nextArrInt(int n) throws IOException {
			int[] a = new int[n];
			for (int i = 0; i < n; i++)
				a[i] = nextInt();
			return a;
		}

		public long[] nextArrLong(int n) throws IOException {
			long[] a = new long[n];
			for (int i = 0; i < n; i++)
				a[i] = nextLong();
			return a;
		}

		public boolean ready() throws IOException {
			return br.ready();
		}

		public void waitForInput() throws InterruptedException {
			Thread.sleep(3000);
		}
	}
}