WA 了/kk
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 5e4 + 5, N4 = 2e5 + 5;
int n, m, a[N];
struct node{
int lx = 0, rx = 0, ans = 0, lt = 0, rt = 0;
friend node operator +(const node &a, const node &b) {
node c;
c.lx = a.lx; if(a.lx == a.rt - a.lt + 1) c.lx += b.lx;
c.rx = b.rx; if(b.rx == b.rt - b.lt + 1) c.rx += a.rx;
c.ans = max(a.ans, max(b.ans, a.rx + b.lx));
return c;
}
}tr[N4];
void pushup(int cur) {
tr[cur] = tr[cur << 1] + tr[cur << 1 | 1];
return ;
}
void build(int cur, int lt, int rt) {
if(lt == rt) {
tr[cur].lx = tr[cur].rx = tr[cur].ans = a[lt];
tr[cur].lt = tr[cur].rt = lt;
return ;
}
int mid = (lt + rt) >> 1;
build(cur << 1, lt, mid);
build(cur << 1 | 1, mid + 1, rt);
pushup(cur);
return ;
}
node query(int cur, int lt, int rt, int qx, int qy) {
node ret;
if(lt > qy || rt < qx) return ret;
if(lt >= qx && rt <= qy) return tr[cur];
int mid = (lt + rt) >> 1;
return query(cur << 1, lt, mid, qx, qy) + query(cur << 1 | 1, mid + 1, rt, qx, qy);
}
signed main() {
scanf("%lld", &n);
for (int i = 1; i <= n; ++i) scanf("%lld", &a[i]);
build(1, 1, n);
scanf("%lld", &m);
for (int i = 1; i <= m; ++i) {
int x, y; scanf("%lld%lld", &x, &y);
printf("%lld\n", query(1, 1, n, x, y).ans);
}
return 0;
}