RT，写的是那个猫树好像。

根据别人的博客瞎胡的写法，不知道对不对，讨论区的hack和样例都能过啊qwq

求助求助求助

//#include<bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <math.h>
#include <algorithm>
#include <istream>
#include <string>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <string.h>
#include <map>
#include <unordered_map>
#include <sstream>
#include <bitset>
using namespace std;
#define endl "\n"
#define int long long
//#define double long double
#define p1(x) (x).first
#define p2(x) (x).second
#define pii pair<int,int>
#define lc(x) ((x)<<1)
#define rc(x) ((x)<<1|1)
//#pragma optimize(3)
//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
const int LG=18;
const int N=262144;
int p[LG+2][N+10],s[LG+2][N+10];
int pANS[LG+2][N+10],sANS[LG+2][N+10];
int pw[LG+2][N+10],sw[LG+2][N+10];
int pmx[LG+2][N+10],smx[LG+2][N+10];
int a[N+10];
int n;
int lg[N+10];

inline void bd(int k=0,int l=0,int r=N-1){
    if(l==r){
        p[k][l]=max(0ll,a[l]);
        s[k][l]=max(0ll,a[l]);
        pANS[k][l]=sANS[k][l]=max(0ll,a[l]);
        pw[k][l]=sw[k][l]=a[l];
        pmx[k][l]=smx[k][l]=a[l];
        return ;
    }
    int mid=l+r>>1;
    bd(k+1,l,mid);
    bd(k+1,mid+1,r);
    for(int i=l;i<=mid;i++)
        p[k][i]=p[k+1][i],
        pw[k][i]=pw[k+1][i],
        pmx[k][i]=pmx[k+1][i],
        pANS[k][i]=pANS[k+1][i];
    for(int i=mid+1;i<=r;i++)
        p[k][i]=max(pw[k+1][mid]+p[k+1][i],p[k][i-1]),
        pw[k][i]=pw[k+1][mid]+pw[k+1][i],
        pmx[k][i]=max(pmx[k+1][mid],pmx[k+1][i]),
        pANS[k][i]=max(pANS[k][i-1],p[k+1][i]+s[k+1][l]);
    
    for(int i=r;i>=mid+1;i--)
        s[k][i]=s[k+1][i],
        sw[k][i]=sw[k+1][i],
        smx[k][i]=smx[k+1][i],
        sANS[k][i]=sANS[k+1][i];
    for(int i=mid;i>=l;i--)
        s[k][i]=max(sw[k+1][mid+1]+s[k+1][i],s[k][i+1]),
        sw[k][i]=sw[k+1][i]+sw[k+1][mid+1],
        smx[k][i]=max(smx[k+1][mid+1],smx[k+1][i]),
        sANS[k][i]=max(sANS[k][i+1],s[k+1][i]+p[k+1][r]);
}
inline int g(int l,int r){
    if(l==r)return a[l];
    int k=LG-lg[l^r];
    int MX=max(smx[k][l],pmx[k][r]);
    if(MX<=0)return MX;
    return max(max(sANS[k][l],pANS[k][r]),s[k][l]+p[k][r]);
}
inline void slv(){
    lg[0]=-1;
    for(int i=1;i<N;i++)
        lg[i]=lg[i>>1]+1;
    cin>>n;
    memset(a,-0x3f,sizeof(a));
    for(int i=0;i<n;i++)
        cin>>a[i];
    bd();
    int q;
    cin>>q;
    while(q--){
        int l,r;
        cin>>l>>r;
        l--,r--;
        cout<<g(l,r)<<endl;
    }
}

inline void MT(){long long _;cin>>_;while(_--)slv();}
const char* SS="/Users/noip2019/Downloads/problem_2612/ex_rectangle4.in";
signed main(){ios::sync_with_stdio(0);
//     freopen(SS,"r",stdin);
//    MT();
    slv();
    return 0;
}