Language: C++

#include <cstdio>
#include <algorithm>

#define int long long

const int maxn = 3e5 + 10;

const long long oo = 1ll << 62;

int n;
long long t[maxn], dpl[maxn], dpr[maxn], w[maxn], T[maxn];

inline bool check(long long x0, long long y0, long long x1, long long y1, long long x2, long long y2) {
	long long a = x1 - x0, b = y1 - y0, c = x2 - x1, d = y2 - y1;
	return a * d - b * c >= 0;
}

inline void pre_calc(long long *dp) {
	static long long T[maxn], x[maxn], y[maxn];
	static int top, chs;
	top = chs = 0;
	x[top] = 0;
	y[top] = 0;
	dp[0] = 0;
	++top;
	for (int i = 1; i <= n; ++i) {
		T[i] = T[i - 1] + t[i];
		if(chs >= top) {
			chs = top - 1;
		}
		while(chs - 1 >= 0 && x[chs - 1] * -i + y[chs - 1] >= x[chs] * -i + y[chs]) {
			--chs;
		}
		while(chs + 1 < top && x[chs + 1] * -i + y[chs + 1] >= x[chs] * -i + y[chs]) {
			++chs;
		}
		dp[i] = std::max(dp[i - 1], x[chs] * -i + y[chs] + (long long) i * (i + 1) / 2 - T[i]);
		long long nx = i, ny = dp[i] + T[i] + (long long)  i * (i - 1) / 2;
		while(top > 1 && check(x[top - 2], y[top - 2], x[top - 1], y[top - 1], nx, ny)) {
			--top;
		}
		x[top] = nx;
		y[top] = ny;
		++top;
	}
	return;
}

inline void dc(int l, int r) {
	static long long x[maxn], y[maxn], dp[maxn];
	static int top;

	if(l == r) {
		w[l] = dpl[l - 1] + dpr[r + 1] + 1 - t[l];
		return;
	}
	int mid = l + r >> 1;
	dc(l, mid);
	dc(mid + 1, r);

#ifdef DEBUG
	printf("dc(%d, %d)\n", l, r);
#endif
	//solve w[mid + 1 ... r]
	top = 0;
	for (int i = l; i <= mid; ++i) {
		long long nx = i, ny = dpl[i - 1] + T[i - 1] + (long long) l * (l - 1) / 2 - l;
		while(top > 1 && check(x[top - 2], y[top - 2], x[top - 1], y[top - 1], nx, ny)) {
			--top;
		}
		x[top] = nx;
		y[top] = ny;
		++top;
	}
	for (int i = r, chs = -1; i > mid; --i) {
		dp[i] = -oo;
		if(!~chs) {
			for (int j = 0; j < top; ++j) {
				if(x[j] * -i + y[j] > dp[i]) {
					dp[i] = x[j] * -i + y[j];
					chs = j;
				}
			}
			dp[i] += (long long) i * (i + 1) / 2 + i + dpr[i + 1] - T[i] + 1;
			w[i] = std::max(w[i], dp[i]);
		}
		else {
			while(chs - 1 >= 0 && x[chs - 1] * -i + y[chs - 1] >= x[chs] * -i + y[chs]) {
				--chs;
			}
			while(chs + 1 < top && x[chs + 1] * -i + y[chs + 1] >= x[chs] * -i + y[chs]) {
				++chs;
			}
			dp[i] = x[chs] * -i + y[chs];
			dp[i] += (long long) i * (i + 1) / 2 + i + dpr[i + 1] - T[i] + 1;
			dp[i] = std::max(dp[i], dp[i + 1]);
			w[i] = std::max(w[i], dp[i]);
		}
#ifdef DEBUG
		printf("\tdp[%d] = %lld\n", i, dp[i]);
#endif
	}

	//solve w[l ... mid]
	top = 0;
	for (int i = mid + 1; i <= r; ++i) {
		long long nx = i, ny = dpr[i + 1] - T[i] + (long long) i * (i + 1) / 2 + i;
		while(top > 1 && check(x[top - 2], y[top - 2], x[top - 1], y[top - 1], nx, ny)) {
			--top;
		}
		x[top] = nx;
		y[top] = ny;
		++top;
	}
	for (int i = l, chs = -1; i <= mid; ++i) {
		dp[i] = -oo;
		if(!~chs) {
			for (int j = 0; j < top; ++j) {
				if(x[j] * -i + y[j] > dp[i]) {
					dp[i] = x[j] * -i + y[j];
					chs = j;
				}
			}
			dp[i] += dpl[i - 1] + T[i - 1] + (long long) i * (i - 1) / 2 - i + 1;
			w[i] = std::max(w[i], dp[i]);
		}
		else {
			while(chs - 1 >= 0 && x[chs - 1] * -i + y[chs - 1] >= x[chs] * -i + y[chs]) {
				--chs;
			}
			while(chs + 1 < top && x[chs + 1] * -i + y[chs + 1] >= x[chs] * -i + y[chs]) {
				++chs;
			}
			dp[i] = x[chs] * -i + y[chs];
			dp[i] += dpl[i - 1] + T[i - 1] + (long long) i * (i - 1) / 2 - i + 1;
			dp[i] = std::max(dp[i], dp[i - 1]);
			w[i] = std::max(w[i], dp[i]);
		}
#ifdef DEBUG
		printf("\tdp[%d] = %lld\n", i, dp[i]);
#endif
	}

	return;
}

main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i) {
		scanf("%lld", t + i);
		T[i] = T[i - 1] + t[i];
	}
	pre_calc(dpl);
	std::reverse(t + 1, t + n + 1);
	pre_calc(dpr);
	std::reverse(t + 1, t + n + 1);
	std::reverse(dpr + 1, dpr + n + 1);
	dc(1, n);

	int q;
	scanf("%d", &q);
	while(q--) {
		int i;
		long long x;
		scanf("%d%lld", &i, &x);
#ifdef DEBUG
		printf("w[%d] = %lld\n", i, w[i]);
#endif
		printf("%lld\n", std::max(dpl[i - 1] + dpr[i + 1], w[i] + t[i] - x));
	}
	return;
}


Compiler output:
a.cc:147:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  147 | main() {
      | ^~~~
a.cc: In function 'int main()':
a.cc:171:9: error: return-statement with no value, in function returning 'int' [-fpermissive]
  171 |         return;
      |         ^~~~~~