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 A {
	public static void main (String[] args) { new A(); }

	public A() {
		FastScanner fs = new FastScanner();
		PrintWriter out = new PrintWriter(System.out);
		System.err.println("");

		int n = fs.nextInt();
		int q = fs.nextInt();
		
		int[] a = fs.nextIntArray(n);
		int[] needs = new int[n];
		for(int i = 0; i < n; i++) {
			needs[i] = (i+1) - a[i];
			if(needs[i] < 0) needs[i] = oo;
		}
		Query[] qs = new Query[q];
		for(int i = 0; i < q; i++) {
			qs[i] = new Query(fs.nextInt(), fs.nextInt(), i);
		}
		Arrays.sort(qs);
		
		ST vals = new ST(0, n-1, needs);
		ST pts = new ST(0, n-1, new int[n]);
		
		int[] res = new int[q];
		
		int qPtr = 0;
		for(int addIdx = n-1; addIdx >= 0; addIdx--) {
			//add this in then solve all queries that include this as the left end point
			
			while(true) {
				int zero = vals.find(addIdx, n-1);
//				if(addIdx == 0) System.out.println("Z " + zero);
				if(zero < 0) break;
				
				pts.pointSet(zero, 1);
				vals.rangeAdd(zero+1, n-1, -1);
				vals.pointSet(zero, oo);
			}
			
			while(qPtr < q && qs[qPtr].x == addIdx) {
				int id = qs[qPtr].id;
				res[id] = pts.rangeSum(addIdx, n-qs[qPtr].y-1);
				
				qPtr++;
			}
			
//			System.out.println();
		}
		
		for(int x : res) out.println(x);
		
		out.close();
	}
	
	int oo = (int)1e9;
	class ST {
		ST left, right;
		int L, R, min, delta, sum;
		ST(int a, int b, int[] needs) {
			L = a; R = b;
			if(a == b) {
				min = needs[L];
				return;
			}
			int mid = (a + b) / 2;
			left = new ST(a, mid, needs);
			right = new ST(mid+1, b, needs);
			update();
		}
		
		void rangeAdd(int ll, int rr, int val) {
			if(rr < ll) return;
			if(rr < L || R < ll) return;
			if(ll <= L && R <= rr) {
				delta += val;
				return;
			}
			prop();
			
			left.rangeAdd(ll, rr, val);
			right.rangeAdd(ll, rr, val);
			
			update();
		}
		void pointSet(int idx, int val) {
			if(L == R) {
				min = val;
				sum = val;
				return;
			}
			prop();
			
			if(idx <= left.R) left.pointSet(idx, val);
			else right.pointSet(idx, val);
			
			update();
		}
		int find(int ll, int rr) {
			if(rr < ll) return -1;
			if(rr < L || R < ll) return -1;
			
//			System.out.println("> " + getMin() + " on " + L + " " + R + " for range " + ll + " , " + rr);
			
			if(getMin() > 0) return -1;
			if(L == R) {
				return L;
			}
			prop();
			
			int ans = -1;
			int r = right.find(ll, rr);
			if(r >= 0) ans = r;
			if(ans == -1) {
				int l = left.find(ll, rr);
				ans = l;
			}
			
			update();
			
			return ans;
		}
		int rangeSum(int ll, int rr) {
			if(rr < ll) return 0;
			if(rr < L || R < ll) return 0;
			if(ll <= L && R <= rr) return sum;
			return left.rangeSum(ll, rr) + right.rangeSum(ll, rr);
		}
		
		void prop() {
			if(delta == 0) return;
			left.delta += delta;
			right.delta += delta;
			delta = 0;
		}
		int getMin() {
			return min+delta;
		}
		void update() {
			min = Math.min(left.getMin(), right.getMin());
			sum = left.sum+right.sum;
		}
	}
	
	class Query implements Comparable<Query> {
		int x, y, id;
		Query(int a, int b, int i) {
			x = a; y = b;
			id = i;
		}
		public int compareTo(Query q) {
			int c = Integer.compare(q.x, x);
			return c;
		}
	}

	class FastScanner {
		public int BS = 1<<16;
		public char NC = (char)0;
		byte[] buf = new byte[BS];
		int bId = 0, size = 0;
		char c = NC;
		double num = 1;
		BufferedInputStream in;

		public FastScanner() {
			in = new BufferedInputStream(System.in, BS);
		}

		public FastScanner(String s) {
			try {
				in = new BufferedInputStream(new FileInputStream(new File(s)), BS);
			}
			catch (Exception e) {
				in = new BufferedInputStream(System.in, BS);
			}
		}

		public char nextChar(){
			while(bId==size) {
				try {
					size = in.read(buf);
				}catch(Exception e) {
					return NC;
				}                
				if(size==-1)return NC;
				bId=0;
			}
			return (char)buf[bId++];
		}

		public int nextInt() {
			return (int)nextLong();
		}

		public long nextLong() {
			num=1;
			boolean neg = false;
			if(c==NC)c=nextChar();
			for(;(c<'0' || c>'9'); c = nextChar()) {
				if(c=='-')neg=true;
			}
			long res = 0;
			for(; c>='0' && c <='9'; c=nextChar()) {
				res = (res<<3)+(res<<1)+c-'0';
				num*=10;
			}
			return neg?-res:res;
		}

		public double nextDouble() {
			double cur = nextLong();
			return c!='.' ? cur:cur+nextLong()/num;
		}

		public String next() {
			StringBuilder res = new StringBuilder();
			while(c<=32)c=nextChar();
			while(c>32) {
				res.append(c);
				c=nextChar();
			}
			return res.toString();
		}

		public String nextLine() {
			StringBuilder res = new StringBuilder();
			while(c<=32)c=nextChar();
			while(c!='\n') {
				res.append(c);
				c=nextChar();
			}
			return res.toString();
		}

		public boolean hasNext() {
			if(c>32)return true;
			while(true) {
				c=nextChar();
				if(c==NC)return false;
				else if(c>32)return true;
			}
		}
		
		public int[] nextIntArray(int n) {
			int[] res = new int[n];
			for(int i = 0; i < n; i++) res[i] = nextInt();
			return res;
		}
		
	}

}