import sys
input = lambda:sys.stdin.readline()
n,k = map(int,input().split())
p = list(map(int,input().split()))
ku = [0] * (n+2) # 所属的收费区区间序号
l = 0
su = [0] * (n+2) # 包含的完整的收费区区间数量
t = 1
for i in range(1,n+1):
	if i == p[t]-1:
		su[i] = su[i-1] + 1
		t += 1
	else: su[i] = su[i-1]
	if i == p[l]:
		ku[i] = ku[i-1] + 1
		l += 1
	else: ku[i] = ku[i-1]
q = int(input())
for _ in range(q):
	i,j = map(int,input().split())
	if i == j:
		print(1)
	elif ku[i] == ku[j]:
		print(2)
	else: 
		if j<i: i,j = j,i
		if i in p:
			print(2+su[j] - su[i-1])
		else:
			print(2+su[j] - su[i])