联考的原题，被乱搞冲了 $95$，感觉比 CF765F 更适合用来当支配对引入题（如果要问什么乱搞的话，大概就是取出区间内前 $K$ 个数，钦定两个数对在这堆数里面，然后剩下的是一个 RMQ，当然能被卡）。

考虑点对 $l \le x < y < z \le r$，我们的限制是 $y - x \le z - y$。

仔细观察这个式子，如果我们钦定了 $x,\,y$，那么合法的 $z$ 显然是 $[l,\,r]$ 区间的一段后缀。

支配对的思想是这样的：如果点对 $p_1$ 无论如何不可能优秀于 $p_2$，那么任何时刻不再考虑 $p_1$。

对于我们考虑 $p_2$ 一定不劣于 $p_1$ 的条件。

• $p_1$ 如果合法，那么 $p_2$ 必须合法，我们需要的是一定不劣，因此如果我们不考虑 $p_2$ 的合法性直接抛弃 $p_1$，那么我们就可能在这个区间内找不到答案（$p_1$ 被抛弃，$p_2$ 不合法）。

• 如果 $p_1$ 和 $p_2$ 都合法，那么 $p_2$ 的权值一定不小于 $p_1$ 的权值（前置条件）。

• 在两个基础上，我们希望这个严格不劣于的条件越弱越好，这样我们就可以排除更多更平凡的点对，降低我们的复杂度了。

我们来考虑 $p_1 = (x_1,\,y_1,\,z_1)$ 和 $p_2 = (x_2,\,y_2,\,z_2)$。

首先 $x_1 \le x_2 \wedge z_2 \le z_1$，然后 $a_{x_1} + a_{y_1} + a_{z_1} \le a_{x_2} + a_{y_2} + a_{z_2}$。那么 $p_1$ 被 $p_2$ 偏序了。

但是这个条件太强了，考虑能不能弱化一下它。

你发现固定 $x,\,y$，那么 $z$ 一定是一个后缀。

并且 $y - x$ 越小，那么 $z$ 的限制越少，那么如果 $\max a_x + a_y$ 的值不变的情况下，$y - x$ 越小，答案越可能更大（答案至少不会减小）。

那么我们直接让 $p_1 = (x_1,\,y_1)$ 且 $p_2 = (x_2,\,y_2)$，并且 $x_1 \le x_2 < y_2 \le y_1$。

$p_2$ 偏序 $p_1$ 的条件就是 $a_{x_1} + a_{y_1} \le a_{x_2} + a_{y_2}$。

那不妨考虑 $[x_1,\,y_1]$ 内怎么找偏序它的一个点对，很显然，虽然找一个不小于 $a_{x_1}$ 或者 $a_{y_1}$ 的 $a_k$，然后用 $k$ 替换掉较小的那个端点即可。

于是经过若干次这样的操作，最后我们得到的是 $[l,\,r]$，满足 $a_l,\,a_r$ 都比 $(l,\,r)$ 开区间最大值严格大。

这样的区间数一看就知道很少，实际上，求出 $L_i$ 代表 $i$ 之前最后一个比 $a_i$ 大的 $a_{L_i}$，$R_i$ 代表 $i$ 之后第一个比 $a_i$ 大的 $a_{R_i}$。这里使用悬线法可以直接求。

所有区间 $(L_i,\,i],\,[i,\,R_i)$ 显然描述了所有的“满足 $a_l,\,a_r$ 都比 $(l,\,r)$ 开区间最大值严格大的区间”。

这样的区间，显然最多只有 $2n$ 个。

于是现在这些区间就相当于有一个自己的值，并且会贡献到一个区间的后缀上，也就是让一个区间对一个值 $v$ 取 $\max$。就令这些取 $\max$ 的结果为 $b$。

同时每个位置有一个承担 $z$ 的责任，因此还有一个不会变的值 $c_i = a_i$。

扫描线先去掉那个 $l \le x$ 的限制。

然后我们 $[l,\,r]$ 的询问，相当于求 $\max\limits_{l \le i \le r} b_i + c_i$。

考虑线段树进行维护，$c_i$ 不会变，直接维护 $c$ 的最大值，然后再用个额外信息维护答案。这是双半群，是可以维护的。

区间对 $v$ 取 $\max$ 使用 beats？

又没有其它修改操作，标记合并直接让更大的 $v$ 成为标记即可。

时间复杂度 $\Theta((n + Q) \log n)$。

#include <bits/stdc++.h>
#define X first
#define Y second
#define rep(i, a, b) for (int i = a; i <= b; i++)
#define per(i, a, b) for (int i = a; i >= b; i--)
#define pb push_back
#define mp make_pair
#define mid (l + r >> 1)
using namespace std;
typedef long long int ll;
using ull = unsigned long long int;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pq = priority_queue<int>;
using vec = vector<int>;
constexpr int maxn = 5e5 + 10, N = maxn, mod = 1e9 + 7, B = 600; constexpr ll inf = 1e18;
inline ll ksm(ll a, int b = mod - 2) { ll ls = 1; while (b) (b & 1) && (ls = ls * a % mod), a = a * a % mod, b >>= 1; return ls; }
#define ls(x) (x << 1)
#define rs(x) (x << 1 | 1)
struct Node { int mx, tg, v; } t[maxn << 2]; int a[maxn], n, Q;
#define mx(x) (t[x].mx)
#define tg(x) (t[x].tg)
#define val(x) (t[x].v)
inline void up(int x) { mx(x) = max(mx(ls(x)), mx(rs(x))); }
inline void ptg(int x, int k) { tg(x) = max(tg(x), k); mx(x) = max(mx(x), tg(x) + val(x)); }
inline void down(int x) { if (!tg(x)) return; ptg(ls(x), tg(x)), ptg(rs(x), tg(x)); }
void bd(int l, int r, int x) { if (l == r) return void(val(x) = mx(x) = a[l]); bd(l, mid, ls(x)), bd(mid + 1, r, rs(x)), up(x); val(x) = max(val(ls(x)), val(rs(x))); }
void mdf(int l, int r, int ml, int mr, int v, int x) {
	if (ml <= l && r <= mr) return ptg(x, v); down(x);
	ml <= mid && (mdf(l, mid, ml, mr, v, ls(x)), 1), mr > mid && (mdf(mid + 1, r, ml, mr, v, rs(x)), 1); up(x);
}
int qry(int l, int r, int ql, int qr, int x) {
	if (ql <= l && r <= qr) return mx(x); down(x); int ans = 0;
	ql <= mid && (ans = qry(l, mid, ql, qr, ls(x))), qr > mid && (ans = max(ans, qry(mid + 1, r, ql, qr, rs(x)))); return ans;
}
int L[maxn], R[maxn], ans[maxn]; vector<pii> q[maxn]; vec d[maxn];
int main() {
	scanf("%d", &n);
	rep(i, 1, n) scanf("%d", &a[i]), L[i] = R[i] = i;
	rep(i, 1, n) {
		while (L[i] > 1 && a[i] > a[L[i] - 1]) L[i] = L[L[i] - 1];
		if (L[i] - 1 >= 1) d[L[i] - 1].pb(i);
	}
	per(i, n, 1) {
		while (R[i] < n && a[i] > a[R[i] + 1]) R[i] = R[R[i] + 1];
		if (R[i] + 1 <= n) d[i].pb(R[i] + 1);
	}
	bd(1, n, 1); scanf("%d", &Q);
	for (int i = 1, l, r; i <= Q; i++) scanf("%d%d", &l, &r), q[l].pb({ r, i });
	per(l, n, 1) {
		for (int r : d[l]) if (2 * r - l <= n) mdf(1, n, 2 * r - l, n, a[l] + a[r], 1);
		for (pii x : q[l]) ans[x.Y] = qry(1, n, l, x.X, 1);
	}
	rep(i, 1, Q) printf("%d\n", ans[i]);
	return 0;
}