Can you answer these queries I SPOJ - GSS1

You are given a sequence A[1], A[2], …, A[N] . ( |A[i]| ≤ 15007 , 1 ≤ N ≤ 50000 ). A query is defined as follows:

Query(x,y) = Max { a[i]+a[i+1]+…+a[j] ; x ≤ i ≤ j ≤ y }.

Given M queries, your program must output the results of these queries.

Input

The first line of the input file contains the integer N.

In the second line, N numbers follow.

The third line contains the integer M.

M lines follow, where line i contains 2 numbers xi and yi.

Output

Your program should output the results of the M queries, one query per line.

Example

Input:

3

-1 2 3

1

1 2

Output:

2

/*

一开始W.

不知道为啥.

拍了好多组数据都OK.

原来case更新的时候错了.

考虑三种情况.

分别维护GSS,LGSS,RGSS.

分为两种形态:跨区间和不跨区间.

case 1,2:左右段的GSS.

case 3:左段右端与右段左端的GSS和.

一开始更新的时候更新成了该段的左端GSS 右端GSS case3.

画了画图不对吖.

如果跨区间的话这两种情况是包含在case3里边的.

然后这样就忽略了case1,2.

*/

#include<iostream>

#include<cstdio>

#define MAXN 50001

using namespace std;

int n,m,cut;

struct data{

    int l,r,lg,rg,g,sum,size;

    data *lc,*rc;

}tree[MAXN*4];

int read()

{

    int x=0,f=1;char ch=getchar();

    while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}

    while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();

    return x*f;

}

void build(data *k,int l,int r,int now)

{

    k->l=l,k->r=r;

    if(l==r) {k->g=k->lg=k->rg=k->sum=read();return ;}

    int mid=(l+r)>>1;

    k->size=now;

    k->lc=&tree[now*2];

    k->rc=&tree[now*2+1];

    k->lc->size=now*2;

    k->rc->size=now*2+1;

    build(k->lc,l,mid,now*2);

    build(k->rc,mid+1,r,now*2+1);

    k->lg=max(k->lc->lg,k->lc->sum+k->rc->lg);

    k->rg=max(k->rc->rg,k->rc->sum+k->lc->rg);

    k->sum=k->lc->sum+k->rc->sum;

    k->g=max(k->lc->g,max(k->lc->rg+k->rc->lg,k->rc->g));

    return ;

}

data query(data *k,int l,int r,int num)

{

    data xx;

    if(l<=k->l&&k->r<=r) return tree[num];

    int mid=(k->l+k->r)>>1;

    if(l>mid) return query(k->rc,l,r,k->rc->size);

    else if(r<=mid) return query(k->lc,l,r,k->lc->size);

    else {

        data ll=query(k->lc,l,mid,k->lc->size);

        data rr=query(k->rc,mid+1,r,k->rc->size);

        xx.sum=ll.sum+rr.sum;

        xx.lg=max(ll.lg,ll.sum+rr.lg);

        xx.rg=max(rr.rg,rr.sum+ll.rg);

        xx.g=max(ll.g,max(rr.g,ll.rg+rr.lg));

    }

    return xx;

}

int main()

{

    //freopen("1.in","r",stdin);

    //freopen("1.out","w",stdout);

    int x,y;

    n=read();

    build(tree+1,1,n,1);

    m=read();

    while(m--)

    {

        x=read(),y=read();

        data xx=query(tree+1,x,y,1);

        printf("%d\n",xx.g);

    }

    return 0;

}