题意：给定长度为 \(n\) 的序列 \(a\)，\(m\) 次询问，每次询问区间 \([l,r]\) 中选取三个点 \(i,j,k\) 满足 \(l\le i<j<k\le r\) 且 \(j-i\le k-j\)，你需要使得 \(a_i+a_j+a_k\) 最大，输出这个最大值。
数据范围：\(3\le n\le 5\times 10^5\)，\(1\le a_i\le 10^9\)，\(1\le m\le 5\times 10^5\)。

考虑一次全局询问，首先考虑确定 \(i,j\)，对于同一个 \(k\)，若存在 \(i<i'<j\) 且 \(a_{i'}>a_i\)，那么 \(i'\) 优于 \(i\)；同理，若存在 \(i<j'<j\) 且 \(a_{j'}>a_j\)，那么 \(j'\) 优于 \(j\)。

这也就证明了 \((i,j)\) 的数量是 \(O(n)\) 级别的，则考虑用单调栈预处理每个位置左右两边第一个比它大的位置，然后预处理出后缀最大值即可 \(O(n)\) 的时间内解决。

然后我们考虑把询问都离线下来，从大到小枚举左端点 \(i\)，对于每个 \(i\)，通过上述做法预处理出所有 \(j\) 满足，\(j\) 为 \(i\) 右侧第一个大于 \(a_i\) 的位置，或 \(i\) 为 \(j\) 左侧第一个大于 \(a_j\) 的位置，那么对于所有的 \(k\ge 2j-i\)，设 \(f_k\) 表示以 \(k\) 为结尾的三元组的之和的最大值，则 \(f_k\leftarrow \max\{f_k,a_i+a_j+a_k\}\)。那么答案显然为 \([l,r]\) 的 \(f_k\) 最大值。

然后考虑用线段树维护这件事情，设 \(t_x\) 表示 \(x\) 节点 \(f\) 的最大值，\(mx_x\) 表示 \(x\) 节点 \(a\) 的最大值，那么对于一次修改，相当于一段后缀与 \(c+a_i\) 取 \(\max\)，\(c\) 是常数，那么 \(t_x\) 总是取的 \(a_i\) 最大的那个位置，直接用 \(mx\) 更新 \(tx\)。

时间复杂度 \(O(n)\)。

#include<cstdio>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<set>
#include<vector>
#include<queue>
#include<stack>
#include<cstring>
#include<cstdlib>
#include<map>
#include<ctime>
#define rep(i,a,b) for(register int i=a;i<=b;++i)
#define rev(i,a,b) for(register int i=a;i>=b;--i)
#define gra(i,u) for(register int i=head[u];i;i=edge[i].nxt)
#define Clear(a) memset(a,0,sizeof(a))
#define yes puts("YES")
#define no puts("NO")
using namespace std;
typedef long long ll;
const int INF(1e9+10);
const ll LLINF(1e18+10);
inline int read()
{
	int s=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')s=s*10+(ch-'0'),ch=getchar();
	return s*w;
}
template<typename T>
inline T Min(T x,T y){return x<y?x:y;}
template<typename T>
inline T Max(T x,T y){return x>y?x:y;}
template<typename T>
inline void Swap(T&x,T&y){T t=x;x=y;y=t;return;}
template<typename T>
inline T Abs(T x){return x<0?-x:x;}

const int MOD(1e9+7);
template<typename T>
inline T add(T x){return x;}
template<typename T,typename... types>
inline T add(T x,types... y){T z=add<T>(y...);return x+z>=MOD?x+z-MOD:x+z;}
template<typename T>
inline T mul(T x){return x;}
template<typename T,typename... types>
inline T mul(T x,types... y){return (ll)x*mul<T>(y...)%MOD;}
inline int sub(int x,int y){return add(x-y,MOD);}

const int MAXN(5e5+10);

int n,m,a[MAXN];
typedef pair<int,int> P;
vector<int>G[MAXN];
vector<P>ask[MAXN];
int st[MAXN],tp;
ll ans[MAXN];

struct Segment_Tree
{
	ll tree[MAXN*4];
	int maxx[MAXN*4],tag[MAXN*4];
	inline int lc(int p){return p<<1;}
	inline int rc(int p){return p<<1|1;}
	
	inline void push_up(int u)
	{
		maxx[u]=Max(maxx[lc(u)],maxx[rc(u)]);
		tree[u]=Max(tree[lc(u)],tree[rc(u)]);
		return;
	}
	
	inline void lazy_tag(int u,int k)
	{
		tag[u]=Max(tag[u],k);
		tree[u]=Max(tree[u],(ll)maxx[u]+k);
		return;
	}
	
	inline void push_down(int u)
	{
		if(tag[u])
		{
			lazy_tag(lc(u),tag[u]),lazy_tag(rc(u),tag[u]);
			tag[u]=0;
		}
		return;
	}
	
	inline void build(int u,int l,int r)
	{
		tree[u]=-LLINF;
		if(l==r)
		{
			maxx[u]=a[l];
			return;
		}
		int mid=(l+r)>>1;
		build(lc(u),l,mid),build(rc(u),mid+1,r);
		push_up(u);
		return;
	}
	
	inline void update(int u,int l,int r,int ln,int rn,int k)
	{
		if(ln>rn) return; 
		if(ln<=l&&r<=rn)
		{
			lazy_tag(u,k);
			return;
		}
		push_down(u);
		int mid=(l+r)>>1;
		if(ln<=mid) update(lc(u),l,mid,ln,rn,k);
		if(rn>mid) update(rc(u),mid+1,r,ln,rn,k);
		push_up(u);
		return;
	}
	
	inline ll query(int u,int l,int r,int ln,int rn)
	{
		if(ln>rn) return 0;
		ll res(-LLINF);
		if(ln<=l&&r<=rn) return tree[u];
		push_down(u);
		int mid=(l+r)>>1;
		if(ln<=mid) res=query(lc(u),l,mid,ln,rn);
		if(rn>mid) res=Max(res,query(rc(u),mid+1,r,ln,rn));
		return res;
	}
};
Segment_Tree seg;

int main()
{
	freopen("fake.in","r",stdin);
	freopen("fake.out","w",stdout);
	n=read();
	rep(i,1,n) a[i]=read();
	m=read();
	rep(i,1,m)
	{
		int l=read(),r=read();
		ask[l].push_back(make_pair(r,i));
	}
	rep(i,1,n)
	{
		while(tp&&a[st[tp]]<a[i]) --tp;
		if(tp) G[st[tp]].push_back(i);
		st[++tp]=i;
	}
	tp=0;
	rev(i,n,1)
	{
		while(tp&&a[st[tp]]<=a[i]) --tp;
		if(tp) G[i].push_back(st[tp]);
		st[++tp]=i;
	}
	seg.build(1,1,n);
	rev(i,n,1)
	{
		for(auto j:G[i]) seg.update(1,1,n,2*j-i,n,a[i]+a[j]);
		for(auto x:ask[i]) ans[x.second]=seg.query(1,1,n,i,x.first);
	}
	rep(i,1,m) printf("%lld\n",ans[i]);
	return 0;
}
/* things to check
1.  int overflow or long long memory need
2.  recursion/array/binary search/dp/loop bounds
3.  precision
4.  special cases(n=1,bounds)
5.  delete debug statements
6.  initialize(especially multi-tests)
7.  = or == , n or m ,++ or -- , i or j , > or >= , < or <=
8.  keep it simple and stupid
9.  do not delete, use // instead
10. operator priority
11. is there anything extra to output?
12. ...
*/

/* something to think about
1. greedy? dp? searching? dp with matrix/ segment tree? binary search?
2. If contains "not", why not ?????? or few affect?
*/