#include<bits/stdc++.h>
#define ll long long
using namespace std;
#define left(i) (2*i + 1)
#define right(i) (2*i + 2)
#define parent(i) ((i-1)/2)
#include <vector>
template<class T>
class SegmentTree
{
public:
SegmentTree(std::vector<T> data, T value, T (*combine)(T obj1, T obj2));
SegmentTree(T ar[], int n, T value, T (*combine)(T obj1, T obj2));
T query(int l, int r);
void update(int idx, T val);
//TODO lazy propagation
private:
T *tree;
void buildTree(std::vector<T> data);
int segTreeSize;
T valueForExtraNodes;
T (*combine)(T obj1, T obj2);
int calculateSize(int n);
T queryHelper(int l,int r, int st, int ed, int node);
};
template<class T> SegmentTree<T>::SegmentTree(std::vector<T> data,
T value, T (*combine)(T obj1, T obj2))
{
this->combine = combine;
valueForExtraNodes = value;
segTreeSize = calculateSize(data.size());
buildTree(data);
}
template<class T> SegmentTree<T>::SegmentTree(T ar[], int n,
T value, T (*combine)(T obj1, T obj2))
{
this->combine = combine;
valueForExtraNodes = value;
segTreeSize = calculateSize(n);
std::vector<T> data;
for(int i = 0; i < n; i++)
data.push_back(ar[i]);
buildTree(data);
}
template<class T> int SegmentTree<T>::calculateSize(int n)
{
int pow2 = 1;
while( pow2 < n)
{
pow2 = pow2 << 1;
}
return 2*pow2 - 1;
}
template<class T> T SegmentTree<T>::query(int l, int r)
{
int st = 0, ed = segTreeSize/2;
return queryHelper(l, r, st, ed, 0);
}
template<class T> T SegmentTree<T>::queryHelper(int l,int r, int st, int ed, int node)
{
if( (r < st) || (l > ed) || (l > r) )
return valueForExtraNodes;
if(st >= l && ed <= r)
return tree[node];
T leftVal = queryHelper(l, r, st, (st + ed)/2, left(node));
T rightVal = queryHelper(l, r, (st+ed)/2 + 1, ed, right(node));
return combine(leftVal, rightVal);
}
template<class T> void SegmentTree<T>::buildTree(std::vector<T> data)
{
int n = data.size();
tree = new T[segTreeSize];
int extraNodes = (segTreeSize/2 + 1) - n;
for(int i = segTreeSize - 1; i >= 0; i--)
{
if(extraNodes>0)
{
tree[i] = valueForExtraNodes;
extraNodes--;
}
else if(n>0)
{
tree[i] = data[n-1];
n--;
}
else
tree[i] = combine(tree[left(i)], tree[right(i)]);
}
}
template<class T> void SegmentTree<T>::update(int idx, T val)
{
int segTreeIdx = (segTreeSize/2) + idx;
tree[segTreeIdx] = val;
while(parent(segTreeIdx) >= 0)
{
segTreeIdx = parent(segTreeIdx);
if(right(segTreeIdx) < segTreeSize)
tree[segTreeIdx] = combine(tree[left(segTreeIdx)], tree[right(segTreeIdx)]);
if(segTreeIdx == 0)
break;
}
}
struct node
{
int ans; int tot;
int pref;
int suf;
node(){}
node(int val){tot=ans=pref=suf=val;}
};
node combine(node x,node y)
{
node *ptr = new node();
ptr->ans = max(x.ans,y.ans);
ptr->ans = max(ptr->ans,y.pref+x.suf);
ptr->pref = max(x.tot+y.pref,x.pref);
ptr->suf = max(y.tot+x.suf,y.suf);
ptr->tot = x.tot+y.tot;
return *ptr;
}
int main()
{
int t,i,j,n,ans;
cin>>n;
vector<node> v(n);
for(i=0;i<n;i++)
{
cin>>j;
v[i] = node(j);
}
SegmentTree<node> sg(v,node(-20000),combine);
cin>>n;
while(n--)
{
cin>>i>>j;
node as = sg.query(i-1,j-1);
cout<<(as.ans)<<endl;
}
return 0;
}
I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KI2RlZmluZSBsbCBsb25nIGxvbmcKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKI2RlZmluZSBsZWZ0KGkpICgyKmkgKyAxKQojZGVmaW5lIHJpZ2h0KGkpICgyKmkgKyAyKQojZGVmaW5lIHBhcmVudChpKSAoKGktMSkvMikKI2luY2x1ZGUgPHZlY3Rvcj4KCnRlbXBsYXRlPGNsYXNzIFQ+CmNsYXNzIFNlZ21lbnRUcmVlCnsKICAgIHB1YmxpYzoKICAgICAgICBTZWdtZW50VHJlZShzdGQ6OnZlY3RvcjxUPiBkYXRhLCBUIHZhbHVlLCBUICgqY29tYmluZSkoVCBvYmoxLCBUIG9iajIpKTsKICAgICAgICBTZWdtZW50VHJlZShUIGFyW10sIGludCBuLCBUIHZhbHVlLCBUICgqY29tYmluZSkoVCBvYmoxLCBUIG9iajIpKTsKICAgICAgICBUIHF1ZXJ5KGludCBsLCBpbnQgcik7CiAgICAgICAgdm9pZCB1cGRhdGUoaW50IGlkeCwgVCB2YWwpOwogICAgICAgIC8vVE9ETyBsYXp5IHByb3BhZ2F0aW9uCiAgICBwcml2YXRlOgogICAgICAgIFQgKnRyZWU7CiAgICAgICAgdm9pZCBidWlsZFRyZWUoc3RkOjp2ZWN0b3I8VD4gZGF0YSk7CiAgICAgICAgaW50IHNlZ1RyZWVTaXplOwogICAgICAgIFQgdmFsdWVGb3JFeHRyYU5vZGVzOwogICAgICAgIFQgKCpjb21iaW5lKShUIG9iajEsIFQgb2JqMik7CiAgICAgICAgaW50IGNhbGN1bGF0ZVNpemUoaW50IG4pOwogICAgICAgIFQgcXVlcnlIZWxwZXIoaW50IGwsaW50IHIsIGludCBzdCwgaW50IGVkLCBpbnQgbm9kZSk7Cn07Cgp0ZW1wbGF0ZTxjbGFzcyBUPiBTZWdtZW50VHJlZTxUPjo6U2VnbWVudFRyZWUoc3RkOjp2ZWN0b3I8VD4gZGF0YSwKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgVCB2YWx1ZSwgVCAoKmNvbWJpbmUpKFQgb2JqMSwgVCBvYmoyKSkKewogICB0aGlzLT5jb21iaW5lID0gY29tYmluZTsKICAgdmFsdWVGb3JFeHRyYU5vZGVzID0gdmFsdWU7CiAgIHNlZ1RyZWVTaXplID0gY2FsY3VsYXRlU2l6ZShkYXRhLnNpemUoKSk7CiAgIGJ1aWxkVHJlZShkYXRhKTsKfQoKdGVtcGxhdGU8Y2xhc3MgVD4gU2VnbWVudFRyZWU8VD46OlNlZ21lbnRUcmVlKFQgYXJbXSwgaW50IG4sCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgVCB2YWx1ZSwgVCAoKmNvbWJpbmUpKFQgb2JqMSwgVCBvYmoyKSkKewogICB0aGlzLT5jb21iaW5lID0gY29tYmluZTsKICAgdmFsdWVGb3JFeHRyYU5vZGVzID0gdmFsdWU7CiAgIHNlZ1RyZWVTaXplID0gY2FsY3VsYXRlU2l6ZShuKTsKCiAgIHN0ZDo6dmVjdG9yPFQ+IGRhdGE7CiAgIGZvcihpbnQgaSA9IDA7IGkgPCBuOyBpKyspCiAgICAgICAgIGRhdGEucHVzaF9iYWNrKGFyW2ldKTsKCiAgIGJ1aWxkVHJlZShkYXRhKTsKfQoKCnRlbXBsYXRlPGNsYXNzIFQ+IGludCBTZWdtZW50VHJlZTxUPjo6Y2FsY3VsYXRlU2l6ZShpbnQgbikKewogICAgaW50IHBvdzIgPSAxOwogICAgd2hpbGUoIHBvdzIgPCBuKQogICAgewogICAgICAgIHBvdzIgPSBwb3cyIDw8IDE7CiAgICB9CiAgICByZXR1cm4gMipwb3cyIC0gMTsKfQoKdGVtcGxhdGU8Y2xhc3MgVD4gVCBTZWdtZW50VHJlZTxUPjo6cXVlcnkoaW50IGwsIGludCByKQp7CiAgICBpbnQgc3QgPSAwLCBlZCA9IHNlZ1RyZWVTaXplLzI7CiAgICByZXR1cm4gcXVlcnlIZWxwZXIobCwgciwgc3QsIGVkLCAwKTsKfQoKdGVtcGxhdGU8Y2xhc3MgVD4gVCBTZWdtZW50VHJlZTxUPjo6cXVlcnlIZWxwZXIoaW50IGwsaW50IHIsIGludCBzdCwgaW50IGVkLCBpbnQgbm9kZSkKewogICAgaWYoIChyIDwgc3QpIHx8IChsID4gZWQpIHx8IChsID4gcikgKQogICAgICAgIHJldHVybiB2YWx1ZUZvckV4dHJhTm9kZXM7CiAgICBpZihzdCA+PSBsICYmIGVkIDw9IHIpCiAgICAgICAgcmV0dXJuIHRyZWVbbm9kZV07CiAgICBUIGxlZnRWYWwgPSBxdWVyeUhlbHBlcihsLCByLCBzdCwgKHN0ICsgZWQpLzIsIGxlZnQobm9kZSkpOwogICAgVCByaWdodFZhbCA9IHF1ZXJ5SGVscGVyKGwsIHIsIChzdCtlZCkvMiArIDEsIGVkLCByaWdodChub2RlKSk7CiAgICByZXR1cm4gY29tYmluZShsZWZ0VmFsLCByaWdodFZhbCk7Cn0KCnRlbXBsYXRlPGNsYXNzIFQ+IHZvaWQgU2VnbWVudFRyZWU8VD46OmJ1aWxkVHJlZShzdGQ6OnZlY3RvcjxUPiBkYXRhKQp7CiAgIGludCBuID0gZGF0YS5zaXplKCk7CiAgIHRyZWUgPSBuZXcgVFtzZWdUcmVlU2l6ZV07CiAgIGludCBleHRyYU5vZGVzID0gKHNlZ1RyZWVTaXplLzIgKyAxKSAtIG47CiAgIGZvcihpbnQgaSA9IHNlZ1RyZWVTaXplIC0gMTsgaSA+PSAwOyBpLS0pCiAgIHsKICAgICAgIGlmKGV4dHJhTm9kZXM+MCkKICAgICAgICAgICB7CiAgICAgICAgICAgICAgIHRyZWVbaV0gPSB2YWx1ZUZvckV4dHJhTm9kZXM7CiAgICAgICAgICAgICAgIGV4dHJhTm9kZXMtLTsKICAgICAgICAgICB9CiAgICAgICBlbHNlIGlmKG4+MCkKICAgICAgICAgICB7CiAgICAgICAgICAgICAgIHRyZWVbaV0gPSBkYXRhW24tMV07CiAgICAgICAgICAgICAgIG4tLTsKICAgICAgICAgICB9CiAgICAgICBlbHNlCiAgICAgICAgICAgdHJlZVtpXSA9IGNvbWJpbmUodHJlZVtsZWZ0KGkpXSwgdHJlZVtyaWdodChpKV0pOwogICB9Cn0KCnRlbXBsYXRlPGNsYXNzIFQ+IHZvaWQgU2VnbWVudFRyZWU8VD46OnVwZGF0ZShpbnQgaWR4LCBUIHZhbCkKewogICAgaW50IHNlZ1RyZWVJZHggPSAoc2VnVHJlZVNpemUvMikgKyBpZHg7CiAgICB0cmVlW3NlZ1RyZWVJZHhdID0gdmFsOwogICAgd2hpbGUocGFyZW50KHNlZ1RyZWVJZHgpID49IDApCiAgICB7CiAgICAgICAgc2VnVHJlZUlkeCA9IHBhcmVudChzZWdUcmVlSWR4KTsKICAgICAgICBpZihyaWdodChzZWdUcmVlSWR4KSA8IHNlZ1RyZWVTaXplKQogICAgICAgICAgdHJlZVtzZWdUcmVlSWR4XSA9IGNvbWJpbmUodHJlZVtsZWZ0KHNlZ1RyZWVJZHgpXSwgdHJlZVtyaWdodChzZWdUcmVlSWR4KV0pOwogICAgICAgIGlmKHNlZ1RyZWVJZHggPT0gMCkKICAgICAgICAgICAgYnJlYWs7CiAgICB9Cn0KCnN0cnVjdCBub2RlCnsKICAgIGludCBhbnM7IGludCB0b3Q7CiAgICBpbnQgcHJlZjsKICAgIGludCBzdWY7CiAgICBub2RlKCl7fQogICAgbm9kZShpbnQgdmFsKXt0b3Q9YW5zPXByZWY9c3VmPXZhbDt9Cn07Cm5vZGUgY29tYmluZShub2RlIHgsbm9kZSB5KQp7CiAgICBub2RlICpwdHIgPSBuZXcgbm9kZSgpOwogICAgcHRyLT5hbnMgPSBtYXgoeC5hbnMseS5hbnMpOwogICAgcHRyLT5hbnMgPSBtYXgocHRyLT5hbnMseS5wcmVmK3guc3VmKTsKICAgIHB0ci0+cHJlZiA9IG1heCh4LnRvdCt5LnByZWYseC5wcmVmKTsKICAgIHB0ci0+c3VmID0gbWF4KHkudG90K3guc3VmLHkuc3VmKTsKICAgIHB0ci0+dG90ID0geC50b3QreS50b3Q7CiAgICByZXR1cm4gKnB0cjsKfQppbnQgbWFpbigpCnsKICAgIGludCB0LGksaixuLGFuczsKICAgIGNpbj4+bjsKICAgIHZlY3Rvcjxub2RlPiB2KG4pOwogICAgZm9yKGk9MDtpPG47aSsrKQogICAgewogICAgICAgIGNpbj4+ajsKICAgICAgICB2W2ldID0gbm9kZShqKTsKICAgIH0KICAgIFNlZ21lbnRUcmVlPG5vZGU+IHNnKHYsbm9kZSgtMjAwMDApLGNvbWJpbmUpOwogICAgY2luPj5uOwogICAgd2hpbGUobi0tKQogICAgewogICAgICAgIGNpbj4+aT4+ajsKICAgICAgICBub2RlIGFzID0gc2cucXVlcnkoaS0xLGotMSk7CiAgICAgICAgY291dDw8KGFzLmFucyk8PGVuZGw7CiAgICB9CiAgICByZXR1cm4gMDsKfQoK