Let $a_1, \ldots, 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 \le n, q \le 3 \cdot 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 \leq a_i \leq n$) — elements of the array.

The $i$-th of the next $q$ lines contains two integers $x$ and $y$ ($x, y \ge 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 $[\times, \times, \times, 9, 5, 4, 6, 5, 7, 8, 3, 11, \times]$ (we represent $14$ as $\times$ for clarity).

Here is a strategy that removes $5$ elements (the element removed is colored in red):  $[\times, \times, \times, 9, \color{red}{5}, 4, 6, 5, 7, 8, 3, 11, \times]$  $[\times, \times, \times, 9, 4, 6, 5, 7, 8, 3, \color{red}{11}, \times]$  $[\times, \times, \times, 9, 4, \color{red}{6}, 5, 7, 8, 3, \times]$  $[\times, \times, \times, 9, 4, 5, 7, \color{red}{8}, 3, \times]$  $[\times, \times, \times, 9, 4, 5, \color{red}{7}, 3, \times]$  $[\times, \times, \times, 9, 4, 5, 3, \times]$ (final state) 

It is impossible to remove more than $5$ elements, hence the weight is $5$.

Difficulty: HARD

Starter code:

Solutions:
import sys
sys.setrecursionlimit(10 ** 5)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep='\n')

def II():
	return int(sys.stdin.readline())

def MI():
	return map(int, sys.stdin.readline().split())

def LI():
	return list(map(int, sys.stdin.readline().split()))

def LI1():
	return list(map(int1, sys.stdin.readline().split()))

def LLI(rows_number):
	return [LI() for _ in range(rows_number)]

def SI():
	return sys.stdin.readline()[:-1]

class BitSum:

	def __init__(self, n):
		self.n = n + 1
		self.table = [0] * self.n

	def add(self, i, x):
		i += 1
		while i < self.n:
			self.table[i] += x
			i += i & -i

	def sum(self, i):
		i += 1
		res = 0
		while i > 0:
			res += self.table[i]
			i -= i & -i
		return res

	def rank(self, x):
		idx = 0
		for lv in range((self.n - 1).bit_length() - 1, -1, -1):
			mid = idx + (1 << lv)
			if mid >= self.n:
				continue
			if self.table[mid] < x:
				x -= self.table[mid]
				idx += 1 << lv
		return idx

	def mostr(self, x):
		idx = 0
		for lv in range((self.n - 1).bit_length() - 1, -1, -1):
			mid = idx + (1 << lv)
			if mid >= self.n:
				continue
			if self.table[mid] >= x:
				x -= self.table[mid]
				idx += 1 << lv
		return idx - 1
(n, q) = MI()
aa = LI1()
dd = [i - a for (i, a) in enumerate(aa)]
rli = []
for i in range(q):
	(x, y) = MI()
	rli.append((n - y - 1, x, i))
rli.sort()
bit = BitSum(n + 1)
k = 0
ans = [0] * q
for (r, d) in enumerate(dd):
	j = -1
	if d >= 0:
		j = bit.mostr(d)
		if j == n:
			j = r
		bit.add(0, 1)
		bit.add(j + 1, -1)
	while k < q and rli[k][0] == r:
		(r, l, i) = rli[k]
		k += 1
		ans[i] = bit.sum(l)
print(*ans, sep='\n')


class Fenwick:

	def __init__(self, size):
		self.size = size
		self.tree = [0] * (size + 1)

	def add(self, idx, val):
		idx = int(idx)
		while idx <= self.size:
			self.tree[idx] += val
			idx += idx & -idx

	def sum(self, idx):
		ret = 0
		idx = int(idx)
		while idx > 0:
			ret += self.tree[idx]
			idx -= idx & -idx
		return ret
(n, q) = map(int, input().split())
A = [int(x) for x in input().split()]
A = [A[i] - (i + 1) for i in range(n)]
query = [[] for _ in range(n + 1)]
for i in range(q):
	(x, y) = map(int, input().split())
	(l, r) = (x, n - y - 1)
	query[r].append((l, i))
ft = Fenwick(n + 1)
ans = [0 for _ in range(q + 3)]
for r in range(n):
	ob = A[r]
	if ob <= 0:
		if ft.sum(1) >= -ob:
			(low, high) = (0, r)
			while low + 1 < high:
				mid = low + high >> 1
				if ft.sum(mid + 1) >= -ob:
					low = mid
				else:
					high = mid
			idx = high if ft.sum(high + 1) >= -ob else low
			ft.add(1, 1)
			ft.add(idx + 2, -1)
	for qr in query[r]:
		ans[qr[1]] = ft.sum(qr[0] + 1)
for _ in range(q):
	print(ans[_])


mod = 1000000007
eps = 10 ** (-9)

def main():
	import sys
	input = sys.stdin.readline

	class Bit:

		def __init__(self, n):
			self.size = n
			self.tree = [0] * (n + 1)

		def sum(self, i):
			s = 0
			while i > 0:
				s += self.tree[i]
				i -= i & -i
			return s

		def add(self, i, x):
			while i <= self.size:
				self.tree[i] += x
				i += i & -i

		def lower_bound(self, w):
			x = 0
			k = 1 << self.size.bit_length() - 1
			while k:
				if x + k <= self.size and self.tree[x + k] > w:
					w -= self.tree[x + k]
					x += k
				k >>= 1
			return x + 1
	(N, Q) = map(int, input().split())
	A = list(map(int, input().split()))
	A = [i + 1 - A[i] for i in range(N)]
	query = [[] for _ in range(N + 1)]
	ans = [0] * Q
	for q in range(Q):
		(x, y) = map(int, input().split())
		l = x + 1
		r = N - y
		query[r].append((l, q))
	bit = Bit(N + 1)
	for r in range(1, N + 1):
		a = A[r - 1]
		if a == 0:
			bit.add(1, +1)
			bit.add(r + 1, -1)
		elif a > 0:
			k = bit.lower_bound(a - 1)
			if k <= r:
				bit.add(1, +1)
				bit.add(k, -1)
		for (l, q) in query[r]:
			ans[q] = bit.sum(l)
	print(*ans, sep='\n')
main()


import sys
input = sys.stdin.readline
(n, q) = map(int, input().split())
a = list(map(int, input().split()))
a = [i - a[i] + 1 for i in range(n)]
Q = [[] for _ in range(n)]
ans = [-1] * q
for _ in range(q):
	(L, R) = map(int, input().split())
	R = n - 1 - R
	Q[R].append((L, _))
bit = [0] * (n + 1)

def update(idx, val):
	idx = n - 1 - idx
	idx += 1
	while idx < n + 1:
		bit[idx] += val
		idx += idx & -idx

def getSum(idx):
	idx = n - 1 - idx
	idx += 1
	ans = 0
	while idx:
		ans += bit[idx]
		idx -= idx & -idx
	return ans
for R in range(n):
	if a[R] < 0 or getSum(0) < a[R]:
		for (L, i) in Q[R]:
			ans[i] = getSum(L)
		continue
	(lo, hi) = (0, R)
	while lo + 1 < hi:
		mid = (lo + hi) // 2
		if getSum(mid) < a[R]:
			hi = mid
		else:
			lo = mid
	if getSum(hi) >= a[R]:
		update(hi, 1)
	else:
		update(lo, 1)
	for (L, i) in Q[R]:
		ans[i] = getSum(L)
print(*ans)


from sys import stdin

def bitadd(a, w, bit):
	x = a
	while x <= len(bit) - 1:
		bit[x] += w
		x += x & -1 * x

def bitsum(a, bit):
	ret = 0
	x = a
	while x > 0:
		ret += bit[x]
		x -= x & -1 * x
	return ret

class RangeBIT:

	def __init__(self, N, indexed):
		self.bit1 = [0] * (N + 2)
		self.bit2 = [0] * (N + 2)
		self.mode = indexed

	def bitadd(self, a, w, bit):
		x = a
		while x <= len(bit) - 1:
			bit[x] += w
			x += x & -1 * x

	def bitsum(self, a, bit):
		ret = 0
		x = a
		while x > 0:
			ret += bit[x]
			x -= x & -1 * x
		return ret

	def add(self, l, r, w):
		l = l + (1 - self.mode)
		r = r + (1 - self.mode)
		self.bitadd(l, -1 * w * l, self.bit1)
		self.bitadd(r, w * r, self.bit1)
		self.bitadd(l, w, self.bit2)
		self.bitadd(r, -1 * w, self.bit2)

	def sum(self, l, r):
		l = l + (1 - self.mode)
		r = r + (1 - self.mode)
		ret = self.bitsum(r, self.bit1) + r * self.bitsum(r, self.bit2)
		ret -= self.bitsum(l, self.bit1) + l * self.bitsum(l, self.bit2)
		return ret
(n, q) = list(map(int, stdin.readline().split()))
a = list(map(int, stdin.readline().split()))
qs = [[] for i in range(n + 1)]
ans = [None] * q
for loop in range(q):
	(x, y) = list(map(int, stdin.readline().split()))
	l = x + 1
	r = n - y
	qs[r].append((l, loop))
BIT = [0] * (n + 1)
for r in range(1, n + 1):
	b = r - a[r - 1]
	if b >= 0:
		L = 1
		R = r + 1
		while R - L != 1:
			M = (L + R) // 2
			if bitsum(M, BIT) >= b:
				L = M
			else:
				R = M
		if bitsum(L, BIT) >= b:
			bitadd(1, 1, BIT)
			bitadd(L + 1, -1, BIT)
	for (ql, qind) in qs[r]:
		ans[qind] = bitsum(ql, BIT)
for i in ans:
	print(i)


import os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
MaxLength = 2 ** 19
SegmentTree = []
CurLen = MaxLength
while CurLen != 0:
	SegmentTree.append([0] * CurLen)
	CurLen //= 2
Depth = len(SegmentTree)

def addElem(n, index):
	for j in range(Depth):
		if index < len(SegmentTree[j]):
			SegmentTree[j][index] += n
		index //= 2

def firstNSum(n):
	nCpy = n
	summ = 0
	depthCur = 0
	while nCpy != 0:
		if nCpy % 2 != 0:
			summ += SegmentTree[depthCur][nCpy - 1]
		nCpy //= 2
		depthCur += 1
	return summ
(n, q) = map(int, input().split())
a = list(map(int, input().split()))
for i in range(n):
	a[i] = i + 1 - a[i]
ans = [-1] * q
query = []
for i in range(q):
	(x, y) = map(int, input().split())
	query.append((i, x, n - y))
query.sort(key=lambda x: x[2])
currentY = 0
currentTotalSum = 0
for qu in query:
	while currentY < qu[2]:
		if a[currentY] >= 0 and currentTotalSum >= a[currentY]:
			l = 0
			r = currentY + 1
			while l < r:
				m = (l + r) // 2
				if a[currentY] > currentTotalSum - firstNSum(m):
					r = m
				else:
					l = m + 1
			addElem(1, r - 1)
			currentTotalSum += 1
		currentY += 1
	ans[qu[0]] = currentTotalSum - firstNSum(qu[1])
for elem in ans:
	print(elem)


from bisect import *
from collections import *
from math import gcd, ceil, sqrt, floor, inf
from heapq import *
from itertools import *
from operator import add, mul, sub, xor, truediv, floordiv
from functools import *
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def RL():
	return map(int, sys.stdin.readline().rstrip().split())

def RLL():
	return list(map(int, sys.stdin.readline().rstrip().split()))

def N():
	return int(input())
from types import GeneratorType

def bootstrap(f, stack=[]):

	def wrappedfunc(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		else:
			to = f(*args, **kwargs)
			while True:
				if type(to) is GeneratorType:
					stack.append(to)
					to = next(to)
				else:
					stack.pop()
					if not stack:
						break
					to = stack[-1].send(to)
			return to
	return wrappedfunc
farr = [1]
ifa = []

def fact(x, mod=0):
	if mod:
		while x >= len(farr):
			farr.append(farr[-1] * len(farr) % mod)
	else:
		while x >= len(farr):
			farr.append(farr[-1] * len(farr))
	return farr[x]

def ifact(x, mod):
	global ifa
	ifa.append(pow(farr[-1], mod - 2, mod))
	for i in range(x, 0, -1):
		ifa.append(ifa[-1] * i % mod)
	ifa = ifa[::-1]

def per(i, j, mod=0):
	if i < j:
		return 0
	if not mod:
		return fact(i) // fact(i - j)
	return farr[i] * ifa[i - j] % mod

def com(i, j, mod=0):
	if i < j:
		return 0
	if not mod:
		return per(i, j) // fact(j)
	return per(i, j, mod) * ifa[j] % mod

def catalan(n):
	return com(2 * n, n) // (n + 1)

def linc(f, t, l, r):
	while l < r:
		mid = (l + r) // 2
		if t > f(mid):
			l = mid + 1
		else:
			r = mid
	return l

def rinc(f, t, l, r):
	while l < r:
		mid = (l + r + 1) // 2
		if t < f(mid):
			r = mid - 1
		else:
			l = mid
	return l

def ldec(f, t, l, r):
	while l < r:
		mid = (l + r) // 2
		if t < f(mid):
			l = mid + 1
		else:
			r = mid
	return l

def rdec(f, t, l, r):
	while l < r:
		mid = (l + r + 1) // 2
		if t > f(mid):
			r = mid - 1
		else:
			l = mid
	return l

def isprime(n):
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			return False
	return True

def binfun(x):
	c = 0
	for w in arr:
		c += ceil(w / x)
	return c

def lowbit(n):
	return n & -n

def inverse(a, m):
	a %= m
	if a <= 1:
		return a
	return (1 - inverse(m, a) * m) // a % m

class BIT:

	def __init__(self, arr):
		self.arr = arr
		self.n = len(arr) - 1

	def update(self, x, v):
		while x <= self.n:
			self.arr[x] += v
			x += x & -x

	def query(self, x):
		ans = 0
		while x:
			ans += self.arr[x]
			x &= x - 1
		return ans

class smt:

	def __init__(self, l, r, arr):
		self.l = l
		self.r = r
		self.value = (1 << 31) - 1 if l < r else arr[l]
		mid = (l + r) // 2
		if l < r:
			self.left = smt(l, mid, arr)
			self.right = smt(mid + 1, r, arr)
			self.value &= self.left.value & self.right.value

	def setvalue(self, x, val):
		if self.l == self.r:
			self.value = val
			return
		mid = (self.l + self.r) // 2
		if x <= mid:
			self.left.setvalue(x, val)
		else:
			self.right.setvalue(x, val)
		self.value = self.left.value & self.right.value

	def ask(self, l, r):
		if l <= self.l and r >= self.r:
			return self.value
		val = (1 << 31) - 1
		mid = (self.l + self.r) // 2
		if l <= mid:
			val &= self.left.ask(l, r)
		if r > mid:
			val &= self.right.ask(l, r)
		return val

class DSU:

	def __init__(self, n):
		self.c = [-1] * n

	def same(self, x, y):
		return self.find(x) == self.find(y)

	def find(self, x):
		if self.c[x] < 0:
			return x
		self.c[x] = self.find(self.c[x])
		return self.c[x]

	def union(self, u, v):
		(u, v) = (self.find(u), self.find(v))
		if u == v:
			return False
		if self.c[u] < self.c[v]:
			(u, v) = (v, u)
		self.c[u] += self.c[v]
		self.c[v] = u
		return True

	def size(self, x):
		return -self.c[self.find(x)]

class UFS:

	def __init__(self, n):
		self.parent = [i for i in range(n)]
		self.ranks = [0] * n

	def find(self, x):
		if x != self.parent[x]:
			self.parent[x] = self.find(self.parent[x])
		return self.parent[x]

	def union(self, u, v):
		(pu, pv) = (self.find(u), self.find(v))
		if pu == pv:
			return False
		if self.ranks[pu] >= self.ranks[pv]:
			self.parent[pv] = pu
			if self.ranks[pv] == self.ranks[pu]:
				self.ranks[pu] += 1
		else:
			self.parent[pu] = pv

def Prime(n):
	c = 0
	prime = []
	flag = [0] * (n + 1)
	for i in range(2, n + 1):
		if not flag[i]:
			prime.append(i)
			c += 1
		for j in range(c):
			if i * prime[j] > n:
				break
			flag[i * prime[j]] = prime[j]
			if i % prime[j] == 0:
				break
	return prime

def dij(s, graph):
	d = {}
	d[s] = 0
	heap = [(0, s)]
	seen = set()
	while heap:
		(dis, u) = heappop(heap)
		if u in seen:
			continue
		for v in graph[u]:
			if v not in d or d[v] > d[u] + graph[u][v]:
				d[v] = d[u] + graph[u][v]
				heappush(heap, (d[v], v))
	return d

def GP(it):
	return [(ch, len(list(g))) for (ch, g) in groupby(it)]

class DLN:

	def __init__(self, val):
		self.val = val
		self.pre = None
		self.next = None
t = 1
for i in range(t):
	(n, q) = RL()
	a = RLL()
	a = [i + 1 - a[i] for i in range(n)]
	ans = [0] * q
	res = [[] for i in range(1 + n)]
	for i in range(q):
		(x, y) = RL()
		(l, r) = (x + 1, n - y)
		res[r].append((i, l))
	bi = BIT([0] * (n + 1))
	for r in range(1, n + 1):
		if a[r - 1] >= 0:
			(lo, hi) = (0, r)
			while lo < hi:
				mid = (lo + hi + 1) // 2
				tmp = bi.query(n - mid + 1)
				if tmp >= a[r - 1]:
					lo = mid
				else:
					hi = mid - 1
			if lo:
				bi.update(n - lo + 1, 1)
		for (i, l) in res[r]:
			ans[i] = bi.query(n - l + 1)
	for x in ans:
		print(x)