#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
 
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef long double ld; 
typedef tree<ii, null_type, less<ii>, rb_tree_tag, tree_order_statistics_node_update> pbds;

const ll is_query = -(1LL<<62);
struct Line {
    ll m, b;
    mutable function<const Line*()> succ;
    bool operator<(const Line& rhs) const {
        if (rhs.b != is_query) return m < rhs.m;
        const Line* s = succ();
        if (!s) return 0;
        ll x = rhs.m;
        return 1.0L * b - s->b < 1.0L *(s->m - m) * x;
    }
};
struct ConvexHullDynamic : public multiset<Line> { // will maintain upper hull for maximum
    bool bad(iterator y) {
        auto z = next(y);
        if (y == begin()) {
            if (z == end()) return 0;
            return y->m == z->m && y->b <= z->b;
        }
        auto x = prev(y);
        if (z == end()) return y->m == x->m && y->b <= x->b;
        return (x->b - y->b)*1.0L*(z->m - y->m) >= (y->b - z->b)*1.0L*(y->m - x->m);
    }
    void insert_line(ll m, ll b) {
        auto y = insert({ m, b });
        y->succ = [=] { return next(y) == end() ? 0 : &*next(y); };
        if (bad(y)) { erase(y); return; }
        while (next(y) != end() && bad(next(y))) erase(next(y));
        while (y != begin() && bad(prev(y))) erase(prev(y));
    }
    ll eval(ll x) {
        auto l = *lower_bound((Line) { x, is_query });
        return l.m * x + l.b;
    }
};

ll L[333333];
ll a[333333];
ll S[333333];
ll R[333333];
ll ans[333333];

ll sum(int l, int r)
{
	if(l==0) return S[r];
	else return S[r]-S[l-1];
}

ll L2(ll x)
{
	if(x<0) return 0;
	else return (L[x]+S[x]+(ll(x)*ll(x+1))/2);
}

ll R2(ll x)
{
	if(x<=0) return 0;
	else return (R[x]-S[x-1]+(ll(x)*ll(x-1))/2);
}

void solve(int l, int r)
{
	int mid = (l+r)>>1;
	if(r-l<2) return ;
	ConvexHullDynamic ch;
	//fix right hull
	for(int i=mid+1;i<=r;i++)
	{
		ch.insert_line(-i, R2(i));
	}
	ll mx = -ll(1e18);
	for(int i=l;i<=mid;i++)
	{
		if(i>=0) ans[i]=max(ans[i],mx);
		mx = max(mx, ch.eval(i)+L2(i));
	}
	ch.clear();
	//fix left hull
	for(int i=l;i<=mid;i++)
	{
		ch.insert_line(-i,L2(i));
	}
	mx = -ll(1e18);
	for(int i=r;i>=mid+1;i--)
	{
		if(i>=0) ans[i]=max(ans[i],mx);
		mx = max(mx, ch.eval(i)+R2(i));
	}
	solve(l,mid); solve(mid+1,r);
}

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n; cin>>n;
	for(int i=0;i<n;i++)
	{
		cin>>a[i];
		S[i]=a[i];
		if(i>0) S[i]+=S[i-1];
	}
	for(int i=0;i<n;i++)
	{
		ans[i]=-ll(1e18);
	}
	ConvexHullDynamic ch;
	ch.insert_line(1,1);
	for(int i=0;i<n;i++)
	{
		if(i>0) L[i]=L[i-1];
		L[i]=max(L[i],ch.eval(i)+(ll(i)*ll(i+1))/2-S[i]);
		ch.insert_line(-i,L[i]+(ll(i)*ll(i-1))/2+S[i]);
	}
	ch.clear();
	reverse(a,a+n);
	for(int i=0;i<n;i++)
	{
		S[i]=a[i];
		if(i>0) S[i]+=S[i-1];
	}
	ch.insert_line(1,1);
	for(int i=0;i<n;i++)
	{
		if(i>0) R[i]=R[i-1];
		R[i]=max(R[i],ch.eval(i)+(ll(i)*ll(i+1))/2-S[i]);
		ch.insert_line(-i,R[i]+(ll(i)*ll(i-1))/2+S[i]);
	}
	reverse(R,R+n); reverse(a,a+n);
	/*
	for(int i=0;i<n;i++)
	{
		cerr<<L[i]<<' ';
	}
	cerr<<'\n';
	for(int i=0;i<n;i++)
	{
		cerr<<R[i]<<' ';
	}
	cerr<<'\n';
	*/
	for(int i=0;i<n;i++)
	{
		S[i]=a[i];
		if(i>0) S[i]+=S[i-1];
	}
	/*
	for(int i=0;i<n;i++)
	{
		for(int j=-1;j<i;j++)
		{
			for(int k=i+1;k<=n;k++)
			{
				ans[i]=max(ans[i],L2(j)+R2(k)-j*k);
			}
		}
	}
	*/
	solve(-1,n);
	int q; cin>>q;
	for(int z=0;z<q;z++)
	{
		int p,v; cin>>p>>v; p--;
		cout<<max((p>0?L[p-1]:0)+R[p+1], ans[p]+a[p]-v)<<'\n';
	}
}


Measured memory_bytes: 15488