#include <bits/stdc++.h>
using namespace std;

const int N=2e5+5;

struct node
{
	int add,cov; //懒惰标记
	int lc,rc; //左右儿子
	long long sum,Max;
};

vector <pair<int,int> > que[N];
node res[N*35];
int c[N],root,cnt;
long long ans[N];

void pushup(int rt)
{
	res[rt].sum=res[res[rt].lc].sum+res[res[rt].rc].sum;
	res[rt].Max=max(res[res[rt].lc].Max,res[res[rt].rc].Max);
}

void Add(int rt,int L,int R,int cov,int add)
{
	if(cov)
	{
		res[rt].cov=cov;
		res[rt].add=add;
		res[rt].Max=cov+(long long)add*(2*R-1);
		res[rt].sum=(long long)cov*(R-L+1)+(long long)add*(L+R-1)*(R-L+1);
		return;
	}

	res[rt].add += add;
	res[rt].Max += (long long)add*(2*R-1);
	res[rt].sum += (long long)add*(L+R-1)*(R-L+1);
}

void pushdown(int rt,int L,int R)
{
	if(res[rt].cov || res[rt].add)
	{
		if(!res[rt].lc)
			res[rt].lc=++cnt;

		if(!res[rt].rc)
			res[rt].rc=++cnt;

		int mid=(L+R)/2;
		Add(res[rt].lc,L,mid,res[rt].cov,res[rt].add);
		Add(res[rt].rc,mid+1,R,res[rt].cov,res[rt].add);
		res[rt].cov=res[rt].add=0;
	}
}

void update(int& rt,int l,int r,int ql,int qr,int k)
{
	if(!rt)
		rt=++cnt;

	if(ql<=l && r<=qr)
	{
		Add(rt,l,r,k,0);
		return;
	}

	pushdown(rt,l,r);
	int mid=(l+r)/2;
	if(ql<=mid)
		update(res[rt].lc,l,mid,ql,qr,k);
	if(mid+1<=qr)
		update(res[rt].rc,mid+1,r,ql,qr,k);
	pushup(rt);
}

long long query_sum(int rt,int l,int r,int ql,int qr)
{
	if(!rt)
		return 0;

	if(ql<=l && r<=qr)
		return res[rt].sum;

	pushdown(rt,l,r);
	int mid=(l+r)/2;
	long long ans=0;
	if(ql<=mid)
		ans += query_sum(res[rt].lc,l,mid,ql,qr);
	if(mid+1<=qr)
		ans += query_sum(res[rt].rc,mid+1,r,ql,qr);
	return ans;
}

int query_greater(int rt,int l,int r,int val)
{
	if(res[rt].Max<val)
		return 0;

	if(l==r)
		return l;

	pushdown(rt,l,r);
	int mid=(l+r)/2,lans=query_greater(res[rt].lc,l,mid,val);
	return lans?lans:query_greater(res[rt].rc,mid+1,r,val);
}

int main()
{
	int n,m;
	cin >> n >> m;
	for(int i=1;i<=m;i++)
		scanf("%d",&c[i]);

	int q;
	cin >> q;
	for(int i=1;i<=q;i++)
	{
		int x,y;
		scanf("%d %d",&x,&y);
		que[y].push_back(make_pair(x,i));
	}

	root=1, cnt=1;
	for(int i=1;i<=m;i++)
	{
		if(i>1)
			Add(root,2,n,0,1); //直接全局+等差数列
		else
			Add(root,2,n,c[i],0); //直接全局覆盖

		int pos=query_greater(root,2,n,c[i]);
		if(pos)
			update(root,2,n,pos,n,c[i]);

		for(auto x:que[i])
			if(x.first==1)
				ans[x.second]=i-1;
			else
				ans[x.second]=query_sum(root,2,n,2,x.first)+i-1;
	}

	for(int i=1;i<=q;i++)
		printf("%lld\n",ans[i]);
	return 0;
}