可以暴力枚举 \(a,b\)，然后 \(c\in [2b-a,n]\)，找区间最大值即可。
对于我们选择的 \(a,b\) 间，若能在 \((a,b)\) 中找到某个下标 \(i\)，满足 \(h_i\ge h_a\) 或 \(h_i\ge h_b\)，那么选择 \(i\) 是更优的。
理由很简单，无论是从 \(a\to i\) 还是从 \(b\to i\)，都会扩大 \(c\) 的选择区间，同时还能增大你的 \(h_a+h_b\)。
所以我们只找满足以下条件的 \(a,b\)：
- \([a,b]\) 中最大值 \(< \min\{h_a,h_b\}\)。
这不就是找到一个数，它左右两边的最近的大于等于它的数吗。直接单调栈求出，并且这样的数对是 \(O(n)\) 级别的。
然后我们把询问离线下来，从大到小枚举左端点进行扫描线，对于新的左端点 \(i\)，先把预处理来的数对 \((a,b),a=i\) 对答案进行更新。
如何维护答案？考虑线段树，设 \(B_i\) 表示如果选 \(i\) 作为 \(c\)，它左边的最大的 \(h_a+h_b\)，对于新来的数对 \((a,b)\)，将 \([2b-a,n]\) 中的 \(B_i\) 与 \(h_a+h_b\) 取 \(\max\)，这个用线段树很好维护。
对于左端点为 \(i\) 的所有询问，查询区间 \([i+2,r]\) 的 \(B_i+h_i\) 的最大值。
所以线段树维护 \(h_i,B_i+h_i\) 的最大值，支持与某个数取 \(\max\) 操作，这道题就做完了。
时间复杂度 \(O((n+q)logn)\)。
Code:
#include<bits/stdc++.h>
using namespace std;
#define rd read()
#define PII pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define ll long long
#define FOR(i,j,k) for(int i=j;i<=k;i++)
#define ROF(i,j,k) for(int i=j;i>=k;i--)
int read(){
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)) x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
return x*f;
}
const int N=5e5+10,INF=2e9;
int n,q,stk[N],top,a[N],mx1[N<<2],mx2[N<<2],tag[N<<2],ans[N];
vector<int> v[N];vector<PII> que[N];
void pushdown(int u){
tag[u<<1]=max(tag[u<<1],tag[u]),tag[u<<1|1]=max(tag[u<<1|1],tag[u]);
mx2[u<<1]=max(mx2[u<<1],tag[u]+mx1[u<<1]),mx2[u<<1|1]=max(mx2[u<<1|1],tag[u]+mx1[u<<1|1]);
tag[u]=0;
}
void build(int u,int l,int r){
if(l==r){mx1[u]=mx2[u]=a[l];return;}
int mid=(l+r)>>1;
build(u<<1,l,mid),build(u<<1|1,mid+1,r);
mx1[u]=mx2[u]=max(mx1[u<<1],mx1[u<<1|1]);
}
void modify(int u,int l,int r,int ql,int qr,int val){
if(ql<=l&&r<=qr){
tag[u]=max(tag[u],val),mx2[u]=max(mx2[u],mx1[u]+val);
return;
}
pushdown(u);
int mid=(l+r)>>1;
if(ql<=mid) modify(u<<1,l,mid,ql,qr,val);
if(qr>mid) modify(u<<1|1,mid+1,r,ql,qr,val);
mx2[u]=max(mx2[u<<1],mx2[u<<1|1]);
}
int query(int u,int l,int r,int ql,int qr){
if(ql<=l&&r<=qr) return mx2[u];
pushdown(u);
int mid=(l+r)>>1,ans=0;
if(ql<=mid) ans=max(ans,query(u<<1,l,mid,ql,qr));
if(qr>mid) ans=max(ans,query(u<<1|1,mid+1,r,ql,qr));
return ans;
}
int main(){
n=rd;FOR(i,1,n) a[i]=rd;
a[0]=INF,top=1;
FOR(i,1,n){
while(a[stk[top]]<a[i]) v[stk[top--]].push_back(i);
if(stk[top]) v[stk[top]].push_back(i);
stk[++top]=i;
}
q=rd;
FOR(i,1,q){int l=rd,r=rd;que[l].push_back(mp(r,i));}
build(1,1,n);
ROF(i,n-2,1){
for(auto j:v[i]) if(2*j-i<=n) modify(1,1,n,2*j-i,n,a[i]+a[j]);
for(auto j:que[i]) ans[j.se]=query(1,1,n,i+2,j.fi);
}
FOR(i,1,q) printf("%d\n",ans[i]);
return 0;
}