#include<bits/stdc++.h>
#include<map>
#define ll long long
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
#define vi vector<int>
#define all(a) (a).begin(),(a).end()
#define F first
#define S second
#define sz(x) (int)x.size()
#define hell 1000000007
#define endl '\n'
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rep1(i,a,b) for(ll i=a;i<= b;i++)
#define PI 3.14159
#define MAX 1000001
//sconst ll maxn = (ll)1e18;
using namespace std;
struct node
{
ll sum = LLONG_MIN;
ll bestleftsum = LLONG_MIN;
ll bestrightsum = LLONG_MIN;
ll maxsum = LLONG_MIN;
ll maxvalue = LLONG_MIN;
};
node tree[500005];
ll arr[100005];
void buildtree(ll start,ll end,ll treenode,ll *arr)
{
if(start == end)
{
tree[treenode].maxsum = tree[treenode].sum = tree[treenode].bestleftsum = tree[treenode].bestrightsum = tree[treenode].maxvalue = arr[start];
return;
}
ll mid = (start + end)/2;
buildtree(start,mid,2*treenode,arr);
buildtree(mid+1,end,2*treenode + 1,arr);
node left = tree[2*treenode];
node right = tree[2*treenode + 1];
tree[treenode].sum = left.sum + right.sum;
tree[treenode].bestleftsum = max(left.sum + right.bestleftsum,left.bestrightsum);
tree[treenode].bestrightsum = max(right.sum + left.bestrightsum,right.bestleftsum);
tree[treenode].maxsum = max(max(left.maxsum,right.maxsum),left.bestrightsum + right.bestleftsum);
tree[treenode].maxvalue = max(tree[treenode].sum,max(tree[treenode].bestleftsum,max(tree[treenode].bestrightsum,max(tree[treenode].maxsum,max(left.maxvalue,right.maxvalue)))));
return;
}
void updateArray(ll *arr,ll start,ll end,ll treenode,ll idx,ll value)
{
if(start == end)
{
tree[treenode].maxsum = tree[treenode].sum = tree[treenode].bestleftsum = tree[treenode].bestrightsum = tree[treenode].maxvalue = value;
return;
}
ll mid = start + (end - start)/2;
if(idx > mid)
{
updateArray(arr,mid + 1,end,2*treenode + 1,idx,value);
}
if(idx <= mid)
{
updateArray(arr,start,mid,2*treenode,idx,value);
}
node left = tree[2*treenode];
node right = tree[2*treenode + 1];
tree[treenode].sum = left.sum + right.sum;
tree[treenode].bestleftsum = max(left.sum + right.bestleftsum,left.bestrightsum);
tree[treenode].bestrightsum = max(right.sum + left.bestrightsum,right.bestleftsum);
tree[treenode].maxsum = max(max(left.maxsum,right.maxsum),left.bestrightsum + right.bestleftsum);
tree[treenode].maxvalue = max(tree[treenode].sum,max(tree[treenode].bestleftsum,max(tree[treenode].bestrightsum,max(tree[treenode].maxsum,max(left.maxvalue,right.maxvalue)))));
return;
}
node query(ll* arr,ll start,ll end,ll treenode,ll idx1,ll idx2)
{
node result;
result.sum = result.bestrightsum = result.bestleftsum = result.maxsum = LLONG_MIN;
if(start >= idx1 && end <= idx2)
{
return tree[treenode];
}
if(start > idx2 || end < idx1)
{
return result;
}
ll mid = (start + end)/2;
node left = query(arr,start,mid,2*treenode,idx1,idx2);
node right = query(arr,mid+1,end,2*treenode+1,idx1,idx2);
result.sum = left.sum + right.sum;
result.bestleftsum = max(left.sum + right.bestleftsum,left.bestrightsum);
result.bestrightsum = max(right.sum + left.bestrightsum,right.bestleftsum);
result.maxsum = max(max(left.maxsum,right.maxsum),left.bestrightsum + right.bestleftsum);
result.maxvalue = max(tree[treenode].sum,max(tree[treenode].bestleftsum,max(tree[treenode].bestrightsum,max(tree[treenode].maxsum,max(left.maxvalue,right.maxvalue)))));
return result;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
memset(tree,0,sizeof(tree));
ll n,q;
cin >> n ;
for(ll i = 1; i <= n; i++)
{
cin >> arr[i];
}
cin >> q;
buildtree(1,n,1,arr);
for(ll i = 0; i < q; i++)
{
ll num1,num2;
cin >> num1 >> num2;
cout << query(arr,1,n,1,num1,num2).maxsum << endl;
}
return 0;
}
I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KI2luY2x1ZGU8bWFwPgojZGVmaW5lIGxsICAgICAgICAgIGxvbmcgbG9uZwojZGVmaW5lIHBiICAgICAgICAgIHB1c2hfYmFjawojZGVmaW5lIG1wICAgICAgICAgIG1ha2VfcGFpcgojZGVmaW5lIHBpaSAgICAgICAgIHBhaXI8aW50LGludD4KI2RlZmluZSB2aSAgICAgICAgICB2ZWN0b3I8aW50PgojZGVmaW5lIGFsbChhKSAgICAgIChhKS5iZWdpbigpLChhKS5lbmQoKQojZGVmaW5lIEYgICAgICAgICAgIGZpcnN0CiNkZWZpbmUgUyAgICAgICAgICAgc2Vjb25kCiNkZWZpbmUgc3ooeCkgICAgICAgKGludCl4LnNpemUoKQojZGVmaW5lIGhlbGwgICAgICAgIDEwMDAwMDAwMDcKI2RlZmluZSBlbmRsICAgICAgICAnXG4nCiNkZWZpbmUgcmVwKGksYSxiKSAgZm9yKGludCBpPWE7aTxiO2krKykKI2RlZmluZSByZXAxKGksYSxiKSBmb3IobGwgaT1hO2k8PSBiO2krKykKI2RlZmluZSBQSSAgICAgICAgICAzLjE0MTU5CiNkZWZpbmUgTUFYICAgICAgICAgMTAwMDAwMQovL3Njb25zdCBsbCBtYXhuID0gKGxsKTFlMTg7CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CnN0cnVjdCBub2RlCnsKICBsbCBzdW0gPSBMTE9OR19NSU47CiAgbGwgYmVzdGxlZnRzdW0gPSBMTE9OR19NSU47CiAgbGwgYmVzdHJpZ2h0c3VtID0gTExPTkdfTUlOOwogIGxsIG1heHN1bSA9IExMT05HX01JTjsKICBsbCBtYXh2YWx1ZSA9IExMT05HX01JTjsKfTsKbm9kZSB0cmVlWzUwMDAwNV07CmxsIGFyclsxMDAwMDVdOwp2b2lkIGJ1aWxkdHJlZShsbCBzdGFydCxsbCBlbmQsbGwgdHJlZW5vZGUsbGwgKmFycikKewogIGlmKHN0YXJ0ID09IGVuZCkKICB7CiAgICB0cmVlW3RyZWVub2RlXS5tYXhzdW0gPSB0cmVlW3RyZWVub2RlXS5zdW0gPSB0cmVlW3RyZWVub2RlXS5iZXN0bGVmdHN1bSA9IHRyZWVbdHJlZW5vZGVdLmJlc3RyaWdodHN1bSA9IHRyZWVbdHJlZW5vZGVdLm1heHZhbHVlID0gYXJyW3N0YXJ0XTsKICAgIHJldHVybjsKICB9CiAgbGwgbWlkID0gKHN0YXJ0ICsgZW5kKS8yOwogIGJ1aWxkdHJlZShzdGFydCxtaWQsMip0cmVlbm9kZSxhcnIpOwogIGJ1aWxkdHJlZShtaWQrMSxlbmQsMip0cmVlbm9kZSArIDEsYXJyKTsKICBub2RlIGxlZnQgPSB0cmVlWzIqdHJlZW5vZGVdOwogIG5vZGUgcmlnaHQgPSB0cmVlWzIqdHJlZW5vZGUgKyAxXTsKICB0cmVlW3RyZWVub2RlXS5zdW0gPSBsZWZ0LnN1bSArIHJpZ2h0LnN1bTsKICB0cmVlW3RyZWVub2RlXS5iZXN0bGVmdHN1bSA9IG1heChsZWZ0LnN1bSArIHJpZ2h0LmJlc3RsZWZ0c3VtLGxlZnQuYmVzdHJpZ2h0c3VtKTsKICB0cmVlW3RyZWVub2RlXS5iZXN0cmlnaHRzdW0gPSBtYXgocmlnaHQuc3VtICsgbGVmdC5iZXN0cmlnaHRzdW0scmlnaHQuYmVzdGxlZnRzdW0pOwogIHRyZWVbdHJlZW5vZGVdLm1heHN1bSA9IG1heChtYXgobGVmdC5tYXhzdW0scmlnaHQubWF4c3VtKSxsZWZ0LmJlc3RyaWdodHN1bSArIHJpZ2h0LmJlc3RsZWZ0c3VtKTsKICB0cmVlW3RyZWVub2RlXS5tYXh2YWx1ZSA9IG1heCh0cmVlW3RyZWVub2RlXS5zdW0sbWF4KHRyZWVbdHJlZW5vZGVdLmJlc3RsZWZ0c3VtLG1heCh0cmVlW3RyZWVub2RlXS5iZXN0cmlnaHRzdW0sbWF4KHRyZWVbdHJlZW5vZGVdLm1heHN1bSxtYXgobGVmdC5tYXh2YWx1ZSxyaWdodC5tYXh2YWx1ZSkpKSkpOwogIHJldHVybjsKfQp2b2lkIHVwZGF0ZUFycmF5KGxsICphcnIsbGwgc3RhcnQsbGwgZW5kLGxsIHRyZWVub2RlLGxsIGlkeCxsbCB2YWx1ZSkKewogIGlmKHN0YXJ0ID09IGVuZCkKICB7CiAgICB0cmVlW3RyZWVub2RlXS5tYXhzdW0gPSB0cmVlW3RyZWVub2RlXS5zdW0gPSB0cmVlW3RyZWVub2RlXS5iZXN0bGVmdHN1bSA9IHRyZWVbdHJlZW5vZGVdLmJlc3RyaWdodHN1bSA9IHRyZWVbdHJlZW5vZGVdLm1heHZhbHVlID0gdmFsdWU7CiAgICByZXR1cm47CiAgfQogIGxsIG1pZCA9IHN0YXJ0ICsgKGVuZCAtIHN0YXJ0KS8yOwogIGlmKGlkeCA+IG1pZCkKICB7CiAgICB1cGRhdGVBcnJheShhcnIsbWlkICsgMSxlbmQsMip0cmVlbm9kZSArIDEsaWR4LHZhbHVlKTsKICB9CiAgaWYoaWR4IDw9IG1pZCkKICB7CiAgICB1cGRhdGVBcnJheShhcnIsc3RhcnQsbWlkLDIqdHJlZW5vZGUsaWR4LHZhbHVlKTsKICB9CiAgbm9kZSBsZWZ0ID0gdHJlZVsyKnRyZWVub2RlXTsKICBub2RlIHJpZ2h0ID0gdHJlZVsyKnRyZWVub2RlICsgMV07CiAgdHJlZVt0cmVlbm9kZV0uc3VtID0gbGVmdC5zdW0gKyByaWdodC5zdW07CiAgdHJlZVt0cmVlbm9kZV0uYmVzdGxlZnRzdW0gPSBtYXgobGVmdC5zdW0gKyByaWdodC5iZXN0bGVmdHN1bSxsZWZ0LmJlc3RyaWdodHN1bSk7CiAgdHJlZVt0cmVlbm9kZV0uYmVzdHJpZ2h0c3VtID0gbWF4KHJpZ2h0LnN1bSArIGxlZnQuYmVzdHJpZ2h0c3VtLHJpZ2h0LmJlc3RsZWZ0c3VtKTsKICB0cmVlW3RyZWVub2RlXS5tYXhzdW0gPSBtYXgobWF4KGxlZnQubWF4c3VtLHJpZ2h0Lm1heHN1bSksbGVmdC5iZXN0cmlnaHRzdW0gKyByaWdodC5iZXN0bGVmdHN1bSk7CiAgdHJlZVt0cmVlbm9kZV0ubWF4dmFsdWUgPSBtYXgodHJlZVt0cmVlbm9kZV0uc3VtLG1heCh0cmVlW3RyZWVub2RlXS5iZXN0bGVmdHN1bSxtYXgodHJlZVt0cmVlbm9kZV0uYmVzdHJpZ2h0c3VtLG1heCh0cmVlW3RyZWVub2RlXS5tYXhzdW0sbWF4KGxlZnQubWF4dmFsdWUscmlnaHQubWF4dmFsdWUpKSkpKTsKICByZXR1cm47Cn0Kbm9kZSBxdWVyeShsbCogYXJyLGxsIHN0YXJ0LGxsIGVuZCxsbCB0cmVlbm9kZSxsbCBpZHgxLGxsIGlkeDIpCnsKICBub2RlIHJlc3VsdDsKICByZXN1bHQuc3VtID0gcmVzdWx0LmJlc3RyaWdodHN1bSA9IHJlc3VsdC5iZXN0bGVmdHN1bSA9IHJlc3VsdC5tYXhzdW0gPSBMTE9OR19NSU47CiAgaWYoc3RhcnQgPj0gaWR4MSAmJiBlbmQgPD0gaWR4MikKICB7CiAgICByZXR1cm4gdHJlZVt0cmVlbm9kZV07CiAgfQogIGlmKHN0YXJ0ID4gaWR4MiB8fCBlbmQgPCBpZHgxKQogIHsKICAgIHJldHVybiByZXN1bHQ7CiAgfQogIGxsIG1pZCA9IChzdGFydCArIGVuZCkvMjsKICBub2RlIGxlZnQgPSBxdWVyeShhcnIsc3RhcnQsbWlkLDIqdHJlZW5vZGUsaWR4MSxpZHgyKTsKICBub2RlIHJpZ2h0ID0gcXVlcnkoYXJyLG1pZCsxLGVuZCwyKnRyZWVub2RlKzEsaWR4MSxpZHgyKTsKICByZXN1bHQuc3VtID0gbGVmdC5zdW0gKyByaWdodC5zdW07CiAgcmVzdWx0LmJlc3RsZWZ0c3VtID0gbWF4KGxlZnQuc3VtICsgcmlnaHQuYmVzdGxlZnRzdW0sbGVmdC5iZXN0cmlnaHRzdW0pOwogIHJlc3VsdC5iZXN0cmlnaHRzdW0gPSBtYXgocmlnaHQuc3VtICsgbGVmdC5iZXN0cmlnaHRzdW0scmlnaHQuYmVzdGxlZnRzdW0pOwogIHJlc3VsdC5tYXhzdW0gPSBtYXgobWF4KGxlZnQubWF4c3VtLHJpZ2h0Lm1heHN1bSksbGVmdC5iZXN0cmlnaHRzdW0gKyByaWdodC5iZXN0bGVmdHN1bSk7CiAgcmVzdWx0Lm1heHZhbHVlID0gbWF4KHRyZWVbdHJlZW5vZGVdLnN1bSxtYXgodHJlZVt0cmVlbm9kZV0uYmVzdGxlZnRzdW0sbWF4KHRyZWVbdHJlZW5vZGVdLmJlc3RyaWdodHN1bSxtYXgodHJlZVt0cmVlbm9kZV0ubWF4c3VtLG1heChsZWZ0Lm1heHZhbHVlLHJpZ2h0Lm1heHZhbHVlKSkpKSk7CiAgcmV0dXJuIHJlc3VsdDsKfQppbnQgbWFpbigpCnsKICBpb3NfYmFzZTo6c3luY193aXRoX3N0ZGlvKGZhbHNlKTsKICAgIGNpbi50aWUoMCk7CiAgICBjb3V0LnRpZSgwKTsKICAgIG1lbXNldCh0cmVlLDAsc2l6ZW9mKHRyZWUpKTsKICAgIGxsIG4scTsKICAgIGNpbiA+PiBuIDsKICAgIGZvcihsbCBpID0gMTsgaSA8PSBuOyBpKyspCiAgICB7CiAgICAgIGNpbiA+PiBhcnJbaV07CiAgICB9CiAgICBjaW4gPj4gcTsKICAgIGJ1aWxkdHJlZSgxLG4sMSxhcnIpOwogICAgZm9yKGxsIGkgPSAwOyBpIDwgcTsgaSsrKQogICAgewogICAgICBsbCBudW0xLG51bTI7CiAgICAgIGNpbiA+PiBudW0xID4+IG51bTI7CiAgICAgIGNvdXQgPDwgcXVlcnkoYXJyLDEsbiwxLG51bTEsbnVtMikubWF4c3VtIDw8IGVuZGw7CiAgICB9CiAgICByZXR1cm4gMDsKfQ==