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

#define MAX 300002


int n;

vector<long long int> v;

vector<long long int> dpl;
vector<long long int> dpr;

deque<pair<double, double> > d;

// a/b c/d
pair<double, double> inter(pair<double, double> a, pair<double, double> b) {
	if (a.second > b.second) {
		swap(a, b);
	}
	return make_pair(a.second - b.second, b.first - a.first);
}
bool cmp(pair<double, double> a, pair<double, double> b) {  //a < b
	return a.first*b.second <= a.second*b.first;
}

void add_line(double a, double b) {
	pair<double, double> add = make_pair(a, b);
	while (d.size() > 1) {
		auto t1 = d.front();
		d.pop_front();
		if (cmp(inter(d.front(), t1), inter(d.front(), add))) {
			continue;
		}
		d.push_front(t1);
		break;
	}
	d.push_front(add);
}

double get_val(pair<double, double> a, double x) {
	return a.first*x + a.second;
}

double get_max(double x) {
	while (d.size() > 1) {
		if (get_val(d[0], x) <= get_val(d[1], x)) {
			d.pop_front();
		}
		else {
			break;
		}
	}
	return get_val(d[0], x);
}

void clear() {
	d.clear();
}
void solve(vector<long long int> tim, vector<long long int> &dp) {
	long long int sum = 0;
	clear();
	add_line(-1, 1.0*1.0 / 2.0 - 1.0 / 2.0 + 0 + 0);
	dp.assign(tim.size(), 0);
	vector<long long int> nex = dp;
	long long int su = 0;
	/*for (int i = 0; i < nex.size(); i++) {
	su += v[i];
	long long int w = 0;
	for (int j = -1; j < i; j++) {
	if (j >= 0) {
	w += v[j];
	}
	long long int len = (i - j);
	len *= (1 + len);
	len /= 2LL;
	len -= su;
	len += w;
	if (j >= 0)len += nex[j];
	nex[i] = max(nex[i], len);
	}
	if(i)nex[i] = max(nex[i], nex[i - 1]);
	}*/
	for (int i = 0; i < tim.size(); i++) {
		sum += tim[i];
		double x = i + 2;
		double sum2 = x*x / 2.0 + x / 2.0;
		sum2 += get_max(x);
		sum2 -= sum;
		sum2 = max(sum2, 0.0);
		dp[i] = sum2;
		if (i) {
			dp[i] = max(dp[i], dp[i - 1]);
		}
		add_line(-x, x*x / 2.0 - x / 2.0 + sum + dp[i]);
	}
}

deque<double> V;

double contain[MAX];


void dv(int l, int r, vector<long long int> &tim) {
	int mid = (l + r) >> 1;
	{
		clear();
		long long int sum = 0;
		long long int c = 0;
		if (l) {
			c = dpl[l - 1];
		}
		add_line(-l, l*l / 2.0 - l / 2.0 + sum + c);
		for (int i = l; i < mid; i++) {
			sum += tim[i];
			double x = i + 1;
			add_line(-x, x*x / 2.0 - x / 2.0 + sum + dpl[i]);
		}
		V.clear();
		for (int i = mid; i <= r; i++) {
			sum += tim[i];
			double x = i + 1;
			double sum2 = x*x / 2.0 + x / 2.0;
			sum2 += get_max(x);
			sum2 -= sum;
			if (i + 1 < n) {
				sum2 += dpr[i + 1];
			}
			V.push_back(sum2);
		}
		double mx = V.back();
		for (int i = r; i >= mid; i--) {
			mx = max(mx, V.back());
			V.pop_back();
			contain[i] = max(contain[i], mx);
		}
	}
	///////////////////////
	{
		clear();
		long long int sum = 0;
		long long int c = 0;
		if (r + 1<n) {
			c = dpr[r + 1];
		}
		int base = r + 2;
		int X = base - (r + 1);
		add_line(-X, X*X / 2.0 - X / 2.0 + sum + c);
		for (int i = r; i>mid; i--) {
			sum += tim[i];
			double x = base - i;
			add_line(-x, x*x / 2.0 - x / 2.0 + sum + dpr[i]);
		}
		V.clear();
		for (int i = mid; i >= l; i--) {
			sum += tim[i];
			double x = base - i;
			double sum2 = x*x / 2.0 + x / 2.0;
			sum2 += get_max(x);
			sum2 -= sum;
			if (i) {
				sum2 += dpl[i - 1];
			}
			V.push_back(sum2);
		}
		double mx = V.back();
		for (int i = l; i <= mid; i++) {
			mx = max(mx, V.back());
			V.pop_back();
			contain[i] = max(contain[i], mx);
		}
	}
	if (l < mid) {
		dv(l, mid - 1, tim);
	}
	if (mid < r) {
		dv(mid + 1, r, tim);
	}
}
int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		int a;
		scanf("%d", &a);
		v.push_back(a);
		contain[i] = INT_MIN;
	}
	solve(v, dpl);
	reverse(v.begin(), v.end());
	solve(v, dpr);
	reverse(v.begin(), v.end());
	reverse(dpr.begin(), dpr.end());
	dv(0, n - 1, v);
	int q;
	cin >> q;
	for (int i = 0; i < q; i++) {
		long long int ans = 0;
		int a, b;
		scanf("%d", &a);
		scanf("%d", &b);
		if (a - 1) {
			ans += dpl[a - 1 - 1];
		}
		if (a - 1 + 1 < n) {
			ans += dpr[a - 1 + 1];
		}
		ans = max(ans, (long long int)(contain[a - 1]) + (-b + v[a - 1]));
		printf("%lld\n", ans);
	}
	return 0;
}

Measured memory_bytes: 18208