#include <iostream>
#include <climits>
#define forn(i,a,b) for(int i = a; i < b; i++)
#define boost ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define MAX 1310740
#define M INT_MIN
using namespace std;
struct node
{
long long int prefix{0};
long long int suffix{0};
long long int sum{0};
long long int best{0};
public:
node() = default;
node(long long n)
{
prefix = suffix = sum = best = n;
}
node& operator=(long long n)
{
prefix = suffix = sum = best = n;
return *this;
}
friend ostream& operator<<(ostream&, const node&);
} tree[MAX];
ostream& operator<<(ostream& out, const node& nd)
{
out << "prefix: " << nd.prefix << endl;
out << "suffix: " << nd.suffix << endl;
out << "sum: " << nd.sum << endl;
out << "best: " << nd.best << endl;
return out;
}
void constructST(int arr[], int ss, int se, int si)
{
if(ss > se) return;
if(ss == se)
{
tree[si] = arr[ss];
return;
}
int mid = ss + (se-ss)/2;
constructST(arr, ss, mid, 2*si+1);
constructST(arr, mid+1, se, 2*si+2);
tree[si].best = tree[2*si+1].suffix + tree[2*si+2].prefix;
tree[si].prefix = max(tree[2*si+1].prefix, tree[2*si+2].prefix + tree[2*si+1].sum);
tree[si].suffix = max(tree[2*si+2].suffix, tree[2*si+2].sum + tree[2*si+1].suffix);
tree[si].sum = tree[2*si+1].sum+tree[2*si+2].sum;
if(tree[2*si+1].best > tree[si].best)
{
tree[si].best = tree[2*si+1].best;
}
else if(tree[2*si+2].best > tree[si].best)
{
tree[si].best = tree[2*si+2].best;
}
return;
}
node getmax(int qs, int qe, int ss, int se, int si, int n)
{
//cout << "present index: " << si << endl;
if(ss > qe || se < qs || qs > qe) return node(M);
//cout << ss << " " << se << "\n" << tree[si] << endl;
if(ss >= qs && se <= qe) return tree[si];
int mid = ss + (se-ss)/2;
node left = getmax(qs,qe,ss,mid,2*si+1,n);
node right = getmax(qs,qe,mid+1,se,2*si+2,n);
if(left.best == M) return right;
else if(right.best == M) return left;
node ans(M);
ans.best = max(left.best, right.best);
ans.best = max(ans.best, left.suffix + right.prefix);
ans.prefix = max(left.prefix, left.sum+right.prefix);
ans.suffix = max(right.suffix, right.sum+left.suffix);
ans.sum = left.sum+right.sum;
// if(si == 0)
// {
// cout << left << "\n" << right << "\n" << ans;
// }
return ans;
}
int main()
{
boost;
int n;
cin >> n;
int arr[n];
forn(i,0,n)
{
cin >> arr[i];
}
constructST(arr,0,n-1,0);
int m;
cin >> m;
while(m--)
{
int l, r;
cin >> l >> r;
l--;r--;
cout << getmax(l,r,0,n-1,0,n).best << endl;
}
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8Y2xpbWl0cz4KCiNkZWZpbmUgZm9ybihpLGEsYikgZm9yKGludCBpID0gYTsgaSA8IGI7IGkrKykKI2RlZmluZSBib29zdCBpb3NfYmFzZTo6c3luY193aXRoX3N0ZGlvKDApO2Npbi50aWUoMCk7Y291dC50aWUoMCk7CiNkZWZpbmUgTUFYIDEzMTA3NDAKI2RlZmluZSBNIElOVF9NSU4KCnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgpzdHJ1Y3Qgbm9kZQp7CiAgICBsb25nIGxvbmcgaW50IHByZWZpeHswfTsKICAgIGxvbmcgbG9uZyBpbnQgc3VmZml4ezB9OwogICAgbG9uZyBsb25nIGludCBzdW17MH07CiAgICBsb25nIGxvbmcgaW50IGJlc3R7MH07CnB1YmxpYzoKICAgIG5vZGUoKSA9IGRlZmF1bHQ7CiAgICBub2RlKGxvbmcgbG9uZyBuKQogICAgewogICAgICAgIHByZWZpeCA9IHN1ZmZpeCA9IHN1bSA9IGJlc3QgPSBuOwogICAgfQogICAgbm9kZSYgb3BlcmF0b3I9KGxvbmcgbG9uZyBuKQogICAgewogICAgICAgIHByZWZpeCA9IHN1ZmZpeCA9IHN1bSA9IGJlc3QgPSBuOwogICAgICAgIHJldHVybiAqdGhpczsKICAgIH0KICAgIGZyaWVuZCBvc3RyZWFtJiBvcGVyYXRvcjw8KG9zdHJlYW0mLCBjb25zdCBub2RlJik7Cn0gdHJlZVtNQVhdOwoKb3N0cmVhbSYgb3BlcmF0b3I8PChvc3RyZWFtJiBvdXQsIGNvbnN0IG5vZGUmIG5kKQp7CiAgICBvdXQgPDwgInByZWZpeDogIiA8PCBuZC5wcmVmaXggPDwgZW5kbDsKICAgIG91dCA8PCAic3VmZml4OiAiIDw8IG5kLnN1ZmZpeCA8PCBlbmRsOwogICAgb3V0IDw8ICJzdW06ICIgPDwgbmQuc3VtIDw8IGVuZGw7CiAgICBvdXQgPDwgImJlc3Q6ICIgPDwgbmQuYmVzdCA8PCBlbmRsOwogICAgcmV0dXJuIG91dDsKfQoKdm9pZCBjb25zdHJ1Y3RTVChpbnQgYXJyW10sIGludCBzcywgaW50IHNlLCBpbnQgc2kpCnsKICAgIGlmKHNzID4gc2UpIHJldHVybjsKICAgIGlmKHNzID09IHNlKQogICAgewogICAgICAgIHRyZWVbc2ldID0gYXJyW3NzXTsKICAgICAgICByZXR1cm47CiAgICB9CiAgICBpbnQgbWlkID0gc3MgKyAoc2Utc3MpLzI7CiAgICBjb25zdHJ1Y3RTVChhcnIsIHNzLCBtaWQsIDIqc2krMSk7CiAgICBjb25zdHJ1Y3RTVChhcnIsIG1pZCsxLCBzZSwgMipzaSsyKTsKICAgIHRyZWVbc2ldLmJlc3QgPSB0cmVlWzIqc2krMV0uc3VmZml4ICsgdHJlZVsyKnNpKzJdLnByZWZpeDsKICAgIHRyZWVbc2ldLnByZWZpeCA9IG1heCh0cmVlWzIqc2krMV0ucHJlZml4LCB0cmVlWzIqc2krMl0ucHJlZml4ICsgdHJlZVsyKnNpKzFdLnN1bSk7CiAgICB0cmVlW3NpXS5zdWZmaXggPSBtYXgodHJlZVsyKnNpKzJdLnN1ZmZpeCwgdHJlZVsyKnNpKzJdLnN1bSArIHRyZWVbMipzaSsxXS5zdWZmaXgpOwogICAgdHJlZVtzaV0uc3VtID0gdHJlZVsyKnNpKzFdLnN1bSt0cmVlWzIqc2krMl0uc3VtOwogICAgaWYodHJlZVsyKnNpKzFdLmJlc3QgPiB0cmVlW3NpXS5iZXN0KQogICAgewogICAgICAgIHRyZWVbc2ldLmJlc3QgPSB0cmVlWzIqc2krMV0uYmVzdDsKICAgIH0KICAgIGVsc2UgaWYodHJlZVsyKnNpKzJdLmJlc3QgPiB0cmVlW3NpXS5iZXN0KQogICAgewogICAgICAgIHRyZWVbc2ldLmJlc3QgPSB0cmVlWzIqc2krMl0uYmVzdDsKICAgIH0KICAgIHJldHVybjsKfQoKbm9kZSBnZXRtYXgoaW50IHFzLCBpbnQgcWUsIGludCBzcywgaW50IHNlLCBpbnQgc2ksIGludCBuKQp7CiAgICAvL2NvdXQgPDwgInByZXNlbnQgaW5kZXg6ICIgPDwgc2kgPDwgZW5kbDsKICAgIGlmKHNzID4gcWUgfHwgc2UgPCBxcyB8fCBxcyA+IHFlKSByZXR1cm4gbm9kZShNKTsKICAgIC8vY291dCA8PCBzcyA8PCAiICIgPDwgc2UgPDwgIlxuIiA8PCB0cmVlW3NpXSA8PCBlbmRsOwoKICAgIGlmKHNzID49IHFzICYmIHNlIDw9IHFlKSByZXR1cm4gdHJlZVtzaV07CgogICAgaW50IG1pZCA9IHNzICsgKHNlLXNzKS8yOwoKICAgIG5vZGUgbGVmdCA9IGdldG1heChxcyxxZSxzcyxtaWQsMipzaSsxLG4pOwogICAgbm9kZSByaWdodCA9IGdldG1heChxcyxxZSxtaWQrMSxzZSwyKnNpKzIsbik7CgogICAgaWYobGVmdC5iZXN0ID09IE0pIHJldHVybiByaWdodDsKICAgIGVsc2UgaWYocmlnaHQuYmVzdCA9PSBNKSByZXR1cm4gbGVmdDsKCiAgICBub2RlIGFucyhNKTsKCiAgICBhbnMuYmVzdCA9IG1heChsZWZ0LmJlc3QsIHJpZ2h0LmJlc3QpOwogICAgYW5zLmJlc3QgPSBtYXgoYW5zLmJlc3QsIGxlZnQuc3VmZml4ICsgcmlnaHQucHJlZml4KTsKICAgIGFucy5wcmVmaXggPSBtYXgobGVmdC5wcmVmaXgsIGxlZnQuc3VtK3JpZ2h0LnByZWZpeCk7CiAgICBhbnMuc3VmZml4ID0gbWF4KHJpZ2h0LnN1ZmZpeCwgcmlnaHQuc3VtK2xlZnQuc3VmZml4KTsKICAgIGFucy5zdW0gPSBsZWZ0LnN1bStyaWdodC5zdW07Ci8vICAgIGlmKHNpID09IDApCi8vICAgIHsKLy8gICAgICAgIGNvdXQgPDwgbGVmdCA8PCAiXG4iIDw8IHJpZ2h0IDw8ICJcbiIgPDwgYW5zOwovLyAgICB9CiAgICByZXR1cm4gYW5zOwp9CgppbnQgbWFpbigpCnsKICAgIGJvb3N0OwogICAgaW50IG47CiAgICBjaW4gPj4gbjsKICAgIGludCBhcnJbbl07CiAgICBmb3JuKGksMCxuKQogICAgewogICAgICAgIGNpbiA+PiBhcnJbaV07CiAgICB9CiAgICBjb25zdHJ1Y3RTVChhcnIsMCxuLTEsMCk7CiAgICBpbnQgbTsKICAgIGNpbiA+PiBtOwogICAgd2hpbGUobS0tKQogICAgewogICAgICAgIGludCBsLCByOwogICAgICAgIGNpbiA+PiBsID4+IHI7CiAgICAgICAgbC0tO3ItLTsKICAgICAgICBjb3V0IDw8IGdldG1heChsLHIsMCxuLTEsMCxuKS5iZXN0IDw8IGVuZGw7CiAgICB9Cn0K