#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll seg[200000][4];//sum,prefix,suffix,max
void build(ll seg[][4],ll low,ll high,ll pos,ll arr[])
{
ll mid;
if(low==high)
{
seg[pos][0] = arr[low];//0 for sum
seg[pos][1] = arr[low];//1 for prefix
seg[pos][2] = arr[low];//2 for suffix
seg[pos][3] = arr[low];//3 for best
return;
}
else
{
mid = (low+high)/2;
build(seg,low,mid,(2*pos)+1,arr);
build(seg,mid+1,high,(2*pos)+2,arr);
seg[pos][0] = seg[(2*pos)+1][0] + seg[(2*pos)+2][0];
seg[pos][1] = max(seg[(2*pos)+1][0]+ seg[(2*pos)+2][1],seg[(2*pos)+1][1]);
seg[pos][2] = max(seg[(2*pos)+2][0]+seg[(2*pos)+1][2],seg[(2*pos)+2][2]);
seg[pos][3] = max ( max(seg[(2*pos)+1][3],seg[(2*pos)+2][3]),seg[(2*pos)+1][2]+seg[(2*pos)+2][1]);
return;}
}
ll query(ll seg[][4],ll low,ll high,ll qlow,ll qhigh,ll pos,ll arr[])
{
if(qlow>high || qhigh<low)
{
return -150009;
}
else if(low>=qlow && high<=qhigh)
{
return seg[pos][3];
}
else
{
ll mid;
mid =(low+high)/2;
return (max(query(seg,low,mid,qlow,qhigh,(2*pos)+1,arr),query(seg,mid+1,high,qlow,qhigh,(2*pos)+2,arr)));
}
}
int main()
{
memset(seg,0,sizeof(seg));
ll a,b,c,d,e,f,g,h,i,j,k;
scanf("%lld",&a);
ll arr[a+1];
for(b=0;b<a;b++)
scanf("%lld",&arr[b]);
build(seg,0,a-1,0,arr);
// for(b=0;b<10;b++)
// cout<<seg[b][0]<<" "<<seg[b][1]<<" "<<seg[b][2]<<" "<<seg[b][3]<<"\n";
//cout<<"\n";
scanf("%lld",&c);
for(d=0;d<c;d++)
{
scanf("%lld %lld",&e,&f);
ll po = query(seg,0,a-1,e-1,f-1,0,arr);
printf("%lld\n",po);
}
}
I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKdHlwZWRlZiBsb25nIGxvbmcgIGxsOwpsbCBzZWdbMjAwMDAwXVs0XTsvL3N1bSxwcmVmaXgsc3VmZml4LG1heAoKdm9pZCBidWlsZChsbCBzZWdbXVs0XSxsbCBsb3csbGwgaGlnaCxsbCBwb3MsbGwgYXJyW10pCnsKICAgIGxsIG1pZDsKICAgIGlmKGxvdz09aGlnaCkKICAgIHsKICAgIHNlZ1twb3NdWzBdID0gYXJyW2xvd107Ly8wIGZvciBzdW0KICAgIHNlZ1twb3NdWzFdID0gYXJyW2xvd107Ly8xIGZvciBwcmVmaXgKICAgIHNlZ1twb3NdWzJdID0gYXJyW2xvd107Ly8yIGZvciBzdWZmaXgKICAgIHNlZ1twb3NdWzNdID0gYXJyW2xvd107Ly8zIGZvciBiZXN0CiAgICByZXR1cm47CiAgICB9CiAgICBlbHNlCiAgICB7CiAgICAgICAgbWlkID0gKGxvdytoaWdoKS8yOwogICAgICAgIGJ1aWxkKHNlZyxsb3csbWlkLCgyKnBvcykrMSxhcnIpOwogICAgICAgIGJ1aWxkKHNlZyxtaWQrMSxoaWdoLCgyKnBvcykrMixhcnIpOwogICAgICAgIHNlZ1twb3NdWzBdID0gc2VnWygyKnBvcykrMV1bMF0gKyBzZWdbKDIqcG9zKSsyXVswXTsKICAgICAgICBzZWdbcG9zXVsxXSA9ICBtYXgoc2VnWygyKnBvcykrMV1bMF0rIHNlZ1soMipwb3MpKzJdWzFdLHNlZ1soMipwb3MpKzFdWzFdKTsKICAgICAgICBzZWdbcG9zXVsyXSA9IG1heChzZWdbKDIqcG9zKSsyXVswXStzZWdbKDIqcG9zKSsxXVsyXSxzZWdbKDIqcG9zKSsyXVsyXSk7CiAgICAgICAgc2VnW3Bvc11bM10gPSAgbWF4ICggbWF4KHNlZ1soMipwb3MpKzFdWzNdLHNlZ1soMipwb3MpKzJdWzNdKSxzZWdbKDIqcG9zKSsxXVsyXStzZWdbKDIqcG9zKSsyXVsxXSk7CiAgICByZXR1cm47fQp9CmxsIHF1ZXJ5KGxsIHNlZ1tdWzRdLGxsIGxvdyxsbCBoaWdoLGxsIHFsb3csbGwgcWhpZ2gsbGwgcG9zLGxsIGFycltdKQp7CiAgICBpZihxbG93PmhpZ2ggfHwgcWhpZ2g8bG93KQogICAgewogICAgICAgIHJldHVybiAtMTUwMDA5OwogICAgfQogICAgZWxzZSBpZihsb3c+PXFsb3cgJiYgaGlnaDw9cWhpZ2gpCiAgICB7CiAgICAgICAgcmV0dXJuIHNlZ1twb3NdWzNdOwogICAgfQogICAgZWxzZQogICAgewogICAgbGwgbWlkOwogICAgbWlkID0obG93K2hpZ2gpLzI7CiAgICByZXR1cm4gKG1heChxdWVyeShzZWcsbG93LG1pZCxxbG93LHFoaWdoLCgyKnBvcykrMSxhcnIpLHF1ZXJ5KHNlZyxtaWQrMSxoaWdoLHFsb3cscWhpZ2gsKDIqcG9zKSsyLGFycikpKTsKCiAgICB9Cn0KaW50IG1haW4oKQp7CiAgIG1lbXNldChzZWcsMCxzaXplb2Yoc2VnKSk7CiAgICBsbCBhLGIsYyxkLGUsZixnLGgsaSxqLGs7CiAgICBzY2FuZigiJWxsZCIsJmEpOwogICAgbGwgYXJyW2ErMV07CiAgICBmb3IoYj0wO2I8YTtiKyspCiAgICAgICAgc2NhbmYoIiVsbGQiLCZhcnJbYl0pOwogICAgYnVpbGQoc2VnLDAsYS0xLDAsYXJyKTsKICAgLy8gZm9yKGI9MDtiPDEwO2IrKykKICAgICAvLyAgIGNvdXQ8PHNlZ1tiXVswXTw8IiAiPDxzZWdbYl1bMV08PCIgIjw8c2VnW2JdWzJdPDwiICI8PHNlZ1tiXVszXTw8IlxuIjsKICAgIC8vY291dDw8IlxuIjsKICAgIHNjYW5mKCIlbGxkIiwmYyk7CiAgICBmb3IoZD0wO2Q8YztkKyspCiAgICB7CiAgICAgICAgc2NhbmYoIiVsbGQgJWxsZCIsJmUsJmYpOwogICAgICBsbCBwbyA9IHF1ZXJ5KHNlZywwLGEtMSxlLTEsZi0xLDAsYXJyKTsKICAgICAgcHJpbnRmKCIlbGxkXG4iLHBvKTsKICAgIH0KfQo=