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.
// package CodeForces;

import java.io.BufferedOutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.InputMismatchException;

public class Round668E {	

	public static int oo = (int)1e7;
	public static int oooo = (int)1e8;
	
	
	public static int[] st;
	public static int[] lazy;
	public static int[] sum;
	
	public static void Build(int start, int end, int index, int[] arr) {
		if(start == end) {
			st[index] = arr[start];
			sum[index] = arr[start] >= oo ? 1 : 0;
			return;
		}
		int mid = (start + end)>>1;
		Build(start, mid, index<<1, arr);
		Build(mid + 1, end, index<<1|1, arr);
		if(st[index<<1] < 0) {
			st[index] = st[index<<1];
		}else if(st[index<<1|1] < 0) {
			st[index] = st[index<<1|1];
		}else {
			st[index] = Integer.min(st[index<<1], st[index<<1|1]);
		}
		sum[index] = sum[index<<1|1] + sum[index<<1];
	}
	
	public static void UpdateNode (int start, int end, int index, int i, int value) {
		if(i < start || i > end) {
			return;
		}
		if(lazy[index] != 0) {	
			if(start != end) {
				lazy[index<<1|1] += lazy[index];
				lazy[index<<1] += lazy[index];
			}
			lazy[index] = 0;
		}
		if(start == end) {
			st[index] = value;
			sum[index] = value >= oo ? 1 : 0;
			no_need[start] = true;
//			diff[start] = value;
			return;
		}
		int mid = (start + end)>>1;
		UpdateNode(start, mid, index<<1, i, value);
		UpdateNode(mid + 1, end, index<<1|1, i, value);
		int left = st[index<<1] - lazy[index<<1];
		int right = st[index<<1|1] - lazy[index<<1|1];
		if(left < 0) {
			st[index] = left;
		}else if(right < 0) {
			st[index] = right;
		}else {
			st[index] = Integer.min(left, right);
		}
		sum[index] = sum[index<<1|1] + sum[index<<1];
	}
	
	public static void UpdateRange(int start, int end, int index, int l, int r) {
		if(l > end || start > r) {
			return;
		}
		if(l <= start && end <= r) {
			lazy[index]++;
			if(start != end) {
				lazy[index<<1|1] += lazy[index];
				lazy[index<<1] += lazy[index];
				int left = st[index<<1] - lazy[index<<1];
				int right = st[index<<1|1] - lazy[index<<1|1];
				if(left < 0) {
					st[index] = left;
				}else if(right < 0) {
					st[index] = right;
				}else {
					st[index] = Integer.min(left, right);
				}
			}else {
				st[index] -= lazy[index];
			}
			lazy[index] = 0;
			return;
		}
		if(lazy[index] != 0) {	
			if(start != end) {
				lazy[index<<1|1] += lazy[index];
				lazy[index<<1] += lazy[index];
			}
			lazy[index] = 0;
		}
		int mid = (start + end)>>1;
		UpdateRange(start, mid, index<<1, l, r);
		UpdateRange(mid + 1, end, index<<1|1, l, r);
		int left = st[index<<1] - lazy[index<<1];
		int right = st[index<<1|1] - lazy[index<<1|1];
		if(left < 0) {
			st[index] = left;
		}else if(right < 0) {
			st[index] = right;
		}else {
			st[index] = Integer.min(left, right);
		}
		sum[index] = sum[index<<1|1] + sum[index<<1];
	}

	public static int FirstNeg(int start, int end, int index) {
		if(start == end) {
			st[index] -= lazy[index];
			lazy[index] = 0;
			return st[index] < 0 ? start : oooo;
		}
		boolean go_left = (st[index<<1] - lazy[index<<1]) < 0;
		if(lazy[index] != 0) {	
			if(start != end) {
				lazy[index<<1|1] += lazy[index];
				lazy[index<<1] += lazy[index];
				int left = st[index<<1] - lazy[index<<1];
				int right = st[index<<1|1] - lazy[index<<1|1];
				if(left < 0) {
					st[index] = left;
					go_left = true;
				}else if(right < 0) {
					st[index] = right;
				}else {
					st[index] = Integer.min(left, right);
				}
			}
			lazy[index] = 0;
		}
		if(st[index] >= 0) {
			return oooo;
		}
		if(go_left) {
			return FirstNeg(start, (start + end)>>1, index<<1);
		}else {
			return FirstNeg(((start + end)>>1) + 1, end, index<<1|1);
		}
	}
	
	public static int Sum(int start, int end, int index, int l, int r) {
		if(end < l || start > r) {
			return 0;
		}
		if(l <= start && end <= r) {
			return sum[index];
		}
		int mid = (start + end)>>1;
		return Sum(start, mid, index<<1, l, r) + Sum(mid + 1, end, index<<1|1, l, r);
	}
	
	public static boolean[] no_need;
	public static int[] diff;
	public static void solve() {
		int n = s.nextInt();
		int q = s.nextInt();
		int[] arr = s.nextIntArray(n);
		int[] removable = new int[n];
		removable[0] = arr[0] == 1 ? 1 : 0;
		for(int i = 1; i < n; i++) {
			if(i + 1 >= arr[i] && i - removable[i - 1] + 1 <= arr[i]) {
				removable[i] = 1;
			}
			removable[i] += removable[i - 1];
		}
		int[] del_me = new int[n];
		for(int i = 0; i < n; i++) {
			del_me[i] = i + 1 - arr[i];
		}
		diff = new int[n];
		no_need = new boolean[n];
		if(removable[0] == 1) {
			diff[0] = 0;
		}else {
			diff[0] = oooo;
			no_need[0] = true;
		}
		for(int i = 1; i < n; i++) {
			if(del_me[i] >= 0 && removable[i - 1] >= del_me[i]) {
				diff[i] = removable[i - 1] - del_me[i];
			}else {
				diff[i] = oooo;
				no_need[i] = true;
			}
		}
//		for(int i = 0; i < n; i++) {
//			out.print(diff[i] + " ");
//		}
//		out.println();
		ArrayList<Pair>[] que = new ArrayList[n + 1];
		for(int i = 0; i < n + 1; i++) {
			que[i] = new ArrayList<Pair>();
		}
		for(int i = 0; i < q; i++) {
			int l = s.nextInt();
			int r = n - 1 - s.nextInt();
			que[l].add(new Pair(i, r));
		}
		st = new int[4 * n + 1];
		lazy = new int[4 * n + 1];
		sum = new int[4 * n + 1];
		Build(0, n - 1, 1, diff);
		int[] answer = new int[q];
		for(int i = 0; i < n; i++) {
			for(Pair x : que[i]) {
				answer[x.idx] = x.R - i + 1 - Sum(0, n - 1, 1, i, x.R);
			}
			// remove me
			if(!no_need[i]) {
				int curr = i;
				while(curr < oo) {
					UpdateNode(0, n - 1, 1, curr, oooo);
					UpdateRange(0, n - 1, 1, curr + 1, n - 1);
					curr = FirstNeg(0, n - 1, 1);
				
				}
			}
		}
		for(int i = 0; i < q; i++) {
			out.println(answer[i]);
		}
	}
	
	public static class Pair{
		int idx;
		int R;
		public Pair(int idx, int R) {
			this.idx = idx;
			this.R = R;
		}
	}

	public static void main(String[] args) {
		new Thread(null, null, "Thread", 1 << 27) {
			public void run() {
				try {
					out = new PrintWriter(new BufferedOutputStream(System.out));
					s = new FastReader(System.in);
					solve();
					out.close();
				} catch (Exception e) {
					e.printStackTrace();
					System.exit(1);
				}
			}
		}.start();
	}

	public static PrintWriter out;
	public static FastReader s;

	public static class FastReader {

		private InputStream stream;
		private byte[] buf = new byte[4096];
		private int curChar, snumChars;

		public FastReader(InputStream stream) {
			this.stream = stream;
		}

		public int read() {
			if (snumChars == -1) {
				throw new InputMismatchException();
			}
			if (curChar >= snumChars) {
				curChar = 0;
				try {
					snumChars = stream.read(buf);
				} catch (IOException E) {
					throw new InputMismatchException();
				}
			}
			if (snumChars <= 0) {
				return -1;
			}
			return buf[curChar++];
		}

		public int nextInt() {
			int c = read();
			while (isSpaceChar(c)) {
				c = read();
			}
			int sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = read();
			}
			int number = 0;
			do {
				number *= 10;
				number += c - '0';
				c = read();
			} while (!isSpaceChar(c));
			return number * sgn;
		}

		public long nextLong() {
			int c = read();
			while (isSpaceChar(c)) {
				c = read();
			}
			long sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = read();
			}
			long number = 0;
			do {
				number *= 10L;
				number += (long) (c - '0');
				c = read();
			} while (!isSpaceChar(c));
			return number * sgn;
		}

		public int[] nextIntArray(int n) {
			int[] arr = new int[n];
			for (int i = 0; i < n; i++) {
				arr[i] = this.nextInt();
			}
			return arr;
		}

		public long[] nextLongArray(int n) {
			long[] arr = new long[n];
			for (int i = 0; i < n; i++) {
				arr[i] = this.nextLong();
			}
			return arr;
		}

		public String next() {
			int c = read();
			while (isSpaceChar(c)) {
				c = read();
			}
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(c);
				c = read();
			} while (!isSpaceChar(c));
			return res.toString();
		}

		public String nextLine() {
			int c = read();
			while (isSpaceChar(c)) {
				c = read();
			}
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(c);
				c = read();
			} while (!isEndofLine(c));
			return res.toString();
		}

		public boolean isSpaceChar(int c) {
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}

		public boolean isEndofLine(int c) {
			return c == '\n' || c == '\r' || c == -1;
		}

	}

	
}
