Description

You are given a sequence A of N (N <= 50000) integers between -10000 and 10000. On this sequence you have to apply M (M <= 50000) operations: 

modify the i-th element in the sequence or for given x y print max{Ai + Ai+1 + .. + Aj | x<=i<=j<=y }.

Input

The first line of input contains an integer N. The following line contains N integers, representing the sequence A1..AN. 

The third line contains an integer M. The next M lines contain the operations in following form:

0 x y: modify Ax into y (|y|<=10000).

1 x y: print max{Ai + Ai+1 + .. + Aj | x<=i<=j<=y }.

Output

For each query, print an integer as the problem required.

Example

Input:41 2 3 441 1 30 3 -31 2 41 3 3Output:64-3

---

GSS1加个单点修改

#include 
       
        #include 
        
         #include 
         
          #include 
          
           #define m ((l+r)>>1)#define lson o<<1,l,m#define rson o<<1|1,m+1,r#define lc o<<1#define rc o<<1|1using namespace std;typedef long long ll;const int N=5e5+5,INF=2e9+5;inline int read(){    char c=getchar();int x=0,f=1;    while(c<'0'||c>'9'){
     if(c=='-')f=-1;c=getchar();}    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}    return x*f;}int n,q,op,x,y;struct node{    int sum,mx,pre,suf;}t[N<<2];void merge(int o){    t[o].sum=t[lc].sum+t[rc].sum;    t[o].mx=max(t[lc].suf+t[rc].pre,max(t[lc].mx,t[rc].mx));    t[o].pre=max(t[lc].pre,t[lc].sum+t[rc].pre);    t[o].suf=max(t[rc].suf,t[rc].sum+t[lc].suf);}void build(int o,int l,int r){    if(l==r) t[o].sum=t[o].mx=t[o].pre=t[o].suf=read();    else{        build(lson);        build(rson);        merge(o);    }}int qpre(int o,int l,int r,int ql,int qr){    if(ql<=l&&r<=qr) return t[o].pre;    else if(qr<=m) return qpre(lson,ql,qr);    else return max(qpre(lson,ql,qr),t[lc].sum+qpre(rson,ql,qr));}int qsuf(int o,int l,int r,int ql,int qr){    if(ql<=l&&r<=qr) return t[o].suf;    else if(m