#include <fstream>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#define nmax 550005
using namespace std;
int k,n,m,x,y;
long long sum,sol,a[nmax],b[nmax],s[nmax],c[nmax],val,nr[nmax];
char sir[2000000];
inline long long max(long long z,long long q)
{
if(z>q)return z;
else return q;
}
void actualizare(int ind,int st,int dr)
{ int mij;
if(st==dr){
          a[ind]=b[ind]=c[ind]=max(val,0);
          s[ind]=val;
          }
else {
      mij=(st+dr)/2;
      if(k<=mij)actualizare(2*ind,st,mij);
           else actualizare(2*ind+1,mij+1,dr);
     a[ind]=max(a[2*ind],s[2*ind]+a[2*ind+1]);
     b[ind]=max(b[2*ind+1],b[2*ind]+s[2*ind+1]);
     c[ind]=max(max(c[2*ind],c[2*ind+1]),b[2*ind]+a[2*ind+1]);
     s[ind]=s[2*ind]+s[2*ind+1];
     }

}
void interogare(int ind,int st,int dr)
{ int mij;
if(x<=st&&dr<=y)
        {
        sum=max(sum,0);
        sol=max(sol,max(sum+a[ind],c[ind]));
        sum=max(sum+s[ind],b[ind]);
        }
    else {
         mij=(st+dr)/2;
         if(x<=mij)interogare(2*ind,st,mij);
         if(mij<y)interogare(2*ind+1,mij+1,dr);
         }
}
int main()
{ int i,nr[5];
  char *p;
freopen("maxq.in","r",stdin);
ofstream g("maxq.out");
scanf("%d\n",&n);
gets(sir);
p=strtok(sir," "); k=0;
while(p!=NULL)
    {
    ++k; val=strtol(p,NULL,10);
    actualizare(1,1,n);
    p=strtok(NULL," ");
    }
scanf("%d\n",&m);
for(i=1;i<=m;++i)
    {
   gets(sir); p=strtok(sir," ");
   k=0;
   while(p!=NULL)
    {
    ++k; nr[k]=strtol(p,NULL,10);
    p=strtok(NULL," ");
    }
    x=nr[2]; y=nr[3];
    if(nr[1]==0)
            {
            ++x; k=x; val=y;
            actualizare(1,1,n);
            }
        else {
             ++x; ++y; sum=0; sol=0;
             interogare(1,1,n);
             g<<sol<<"\n";
             }
    }
fclose(stdin);
g.close();
return 0;
}