Part1 暴力
暴力思路：每次询问的时候，枚举 \(a\) 和 \(b\) 在哪里，然后就确定了 \(c\) 的范围 \([2\times b-a]\)，找这个范围内的最大的 A[c] 即可。
Part2优化
舍解
考虑哪一些 \([a,b]\) 是明显不优的。如果存在 \(i\)，满足 \(a<i<b\) 且 \(A[i]<\min(A[a],A[b])\) 那么一定可以缩小 \(a,b\) 中的一个到 \(i\)，缩小之后 \(A[a]+A[b]\) 的值更大，并且 \(b-a\) 更小（给了 \(c\) 更大的范围），所以显然原先的 \([a,b]\) 是不够优秀的。
怎么计算优秀的对？
观察发现，一个点 \(i\) 作为左端点时，第一个 \(j\) 满足 \(j>i,a[j]\ge a[i]\)，能够作为右端点。一个点 \(i\) 作为右端点时，最后一个 \(j\) 满足 \(j<i,a[j]\ge a[j]\)，能够作为左端点。其它的，\(i\) 在端点处的对都是不优的。所以，对每一个 \(i\)，找两侧距离它最近的大于 \(A[i]\) 的值作为端点。可以用单调栈，也可以用链表。
现在优秀的对的数量就是 \(O(n)\) 的。
一次询问的操作
令 \(c[i]\) 表示一个位置 \(i\) 作为 \(c\) 的最大的 \(A[a]+A[b]\).
一次询问就是要在 \([L,R]\) 范围内找最大的 \(c[i]+a[i]\)。
\(a[i]\) 已知，\(c[i]\) 怎么求？
考虑一对 \([a,b]\) 对 \(c\) 数组 的影响。
对于所有 \(i\ge 2\times b-a\) 的，\(c[i]=max(c[i],A[a]+A[b])\)
这不就是区间修改吗？
所以，我们把所有 \(a\ge L\) 的 \([a,b]\) 拿来更新 \(c\) 数组，再询问 \(c\) 数组的某一部分的最大值。单次复杂度为 \(O(n)\)
多次询问
瓶颈是：找所有 \(a\ge L\) 的 \([a,b]\)，怎么优化？离线。
把询问按左端点从大到小排序，枚举 \(L\)，加入 \(L\) 作为左端点的对，更新他们对 \(c\) 的改变。然后更新左端点为 \(L\) 的询问的答案。
Code:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN=5e5+5;
int rd(){
int x=0;bool f=0;char c=getchar();
while(c>'9'||c<'0'){f|=(c=='-');c=getchar();}
while(c<='9'&&c>='0'){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
return f?-x:x;
}
ll a[MAXN];
#define pii pair<int,int>
#define fi first
#define se second
vector<pii> que[MAXN];
int n;
#define lc (u<<1)
#define rc (u<<1|1)
ll C[MAXN<<2],A[MAXN<<2];//c:当前位置作为c，可选的最大的一对数的值 C=max(c)
ll mx[MAXN<<2];//A+C的最大值
ll lz[MAXN<<2];//取max的懒惰标记
inline void upd(int u){
A[u]=max(A[lc],A[rc]);
C[u]=max(C[lc],C[rc]);
mx[u]=max(mx[lc],mx[rc]);
}
void build(int u,int l,int r){
if(l==r){
A[u]=a[l];C[u]=0;mx[u]=A[u];
return;
}
int mid=l+r>>1;
build(lc,l,mid),build(rc,mid+1,r);
upd(u);
}
inline void to(int u,ll v){//用v更新u
C[u]=max(C[u],v);
mx[u]=max(mx[u],A[u]+v);
lz[u]=max(lz[u],v);
}
inline void down(int u){
if(!lz[u]) return;
to(lc,lz[u]),to(rc,lz[u]);
lz[u]=0;
}
void work(int u,int l,int r,int L,int R,int v){
if(r<L||l>R) return;
if(r<=R&&l>=L){
to(u,v);
return;
}
int mid=l+r>>1;down(u);
work(lc,l,mid,L,R,v),work(rc,mid+1,r,L,R,v);
upd(u);
}
ll getmax(int u,int l,int r,int L,int R){
if(r<L||l>R) return 0;
if(r<=R&&l>=L) return mx[u];
int mid=l+r>>1;down(u);
return max(getmax(lc,l,mid,L,R),getmax(rc,mid+1,r,L,R));
}
vector<int> b[MAXN];//a=i时，b[i]中的数可以作为b
int sta[MAXN],tp;
void Pre(){//计算有那些对
for(int i=1;i<=n;i++){
while(tp&&a[sta[tp]]<=a[i]){
b[sta[tp]].push_back(i);//(sta[tp],i)
tp--;
}
sta[++tp]=i;
}
tp=0;
for(int i=n;i>=1;i--){
while(tp&&a[sta[tp]]<=a[i]){
b[i].push_back(sta[tp]);
tp--;
}
sta[++tp]=i;
}
for(int i=1;i<=n;i++){
sort(b[i].begin(),b[i].end());
int cnt=unique(b[i].begin(),b[i].end())-b[i].begin();
// printf("%d\n",cnt);
b[i].resize(cnt);
// for(int j:b[i]) printf("%d %d\n",i,j);
}
}
int ans[MAXN];
int main(){
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++) a[i]=rd();
Pre();
int Q=rd();
for(int i=1;i<=Q;i++){
int l=rd(),r=rd();
que[l].push_back({r,i});
}
build(1,1,n);
for(int i=n;i>=1;i--){
for(int j:b[i]) if(2*j-i<=n)work(1,1,n,2*j-i,n,a[i]+a[j]);
for(pii t:que[i]){
int r=t.fi;
ans[t.se]=getmax(1,1,n,i,r);
}
}
for(int i=1;i<=Q;i++) printf("%d\n",ans[i]);
return 0;
}