#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <complex>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <cassert>
#include <fstream>
#include <utility>
#include <functional>
#define popcount __builtin_popcount
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
template<typename T, bool ismin=true>
struct ConvexHullTrickMonotone{
	using P=pair<T, T>;
	deque<P> deq;
	ConvexHullTrickMonotone(){}
	void add(T a, T b){
		if(!ismin) a*=(-1), b*=(-1);
		if(deq.empty()){
			deq.push_back({a, b});
			return;
		}
		if(deq.back().first>=a){
			if(deq.back().first==a && deq.back().second<=b) return;
			while(deq.size()>1){
				T a1=deq.back().first, b1=deq.back().second;
				T a2=deq[deq.size()-2].first, b2=deq[deq.size()-2].second;
				if((b1-b2)*(a1-a)<(b-b1)*(a2-a1)) break;
				deq.pop_back();
			}
			deq.push_back({a, b});
		}else{
			while(deq.size()>1){
				T a1=deq.front().first, b1=deq.front().second;
				T a2=deq[1].first, b2=deq[1].second;
				if((b1-b2)*(a1-a)>(b-b1)*(a2-a1)) break;
				deq.pop_front();
			}
			deq.push_front({a, b});
		}
	}
	T get(T x, bool isinc){
		if(isinc){
			while(deq.size()>1){
				T a1=deq.front().first, b1=deq.front().second;
				T a2=deq[1].first, b2=deq[1].second;
				if(a1*x+b1<a2*x+b2) break;
				deq.pop_front();
			}
			T ret=deq.front().first*x+deq.front().second;
			if(ismin) return ret;
			else return -ret;
		}else{
			while(deq.size()>1){
				T a1=deq.back().first, b1=deq.back().second;
				T a2=deq[deq.size()-2].first, b2=deq[deq.size()-2].second;
				if(a1*x+b1<a2*x+b2) break;
				deq.pop_back();
			}
			T ret=deq.back().first*x+deq.back().second;
			if(ismin) return ret;
			else return -ret;
		}
	}
	void clear(){
		deq.clear();
	}
};
int n;
ll t[300030];
ll s[300030];
ll dpl[300030], dpr[300030];
ll mx[300030];
void solve(int l, int r){
	if(l>r) return;
	if(l==r){
		mx[l]=max(mx[l], 1-t[l]+dpl[l]+dpr[l+1]);
		return;
	}
	int m=(l+r)/2;
	ConvexHullTrickMonotone<ll, false> cht;
	for(int i=m; i<=r; i++){
		cht.add(-(i+1), dpr[i+1]-s[i+1]+(ll)(i+1)*(i+2)/2);
	}
	ll mx0=-1e18;
	for(int i=l; i<=m; i++){
		mx0=max(mx0, cht.get(i, true)+dpl[i]+(ll)i*(i-1)/2+s[i]);
		mx[i]=max(mx[i], mx0);
	}
	cht.clear();
	for(int i=l; i<=m; i++){
		cht.add(-i, dpl[i]+(ll)i*(i-1)/2+s[i]);
	}
	mx0=-1e18;
	for(int i=r; i>=m; i--){
		mx0=max(mx0, cht.get(i+1, false)+dpr[i+1]+(ll)(i+1)*(i+2)/2-s[i+1]);
		mx[i]=max(mx[i], mx0);
	}
	solve(l, m-1);
	solve(m+1, r);
}
int main()
{
	scanf("%d", &n);
	for(int i=0; i<n; i++){
		scanf("%lld", &t[i]);
		s[i+1]=s[i]+t[i];
		mx[i]=1-t[i];
	}
	ConvexHullTrickMonotone<ll, false> cht;
	cht.add(0, 0);
	for(int i=0; i<n; i++){
		dpl[i+1]=max(dpl[i], cht.get(i+1, true)+(ll)(i+2)*(i+1)/2-s[i+1]);
		cht.add(-i-1, dpl[i+1]+s[i+1]+(ll)(i+1)*i/2);
	}
	cht.clear();
	cht.add(0, 0);
	for(int i=n-1; i>=0; i--){
		dpr[i]=max(dpr[i+1], cht.get(n-i, true)+(ll)(n-i)*(n-i+1)/2-(s[n]-s[i]));
		cht.add(-(n-i), dpr[i]+(s[n]-s[i])+(ll)(n-i)*(n-i-1)/2);
	}
	solve(0, n-1);
	int m;
	scanf("%d", &m);
	for(int i=0; i<m; i++){
		int p; ll x;
		scanf("%d %lld", &p, &x);
		p--;
		printf("%lld\n", max(dpl[p]+dpr[p+1], mx[p]+t[p]-x));
	}
    return 0;
}

Measured memory_bytes: 14336