#include<fstream>

#define lg 100003

using namespace std;

 int n, m, i, x, init[lg], poz, p1, p2, l2, rsp;

 struct arbore_int{
     int x, y, sm, rp;
 };
 arbore_int q[3*lg];

 inline int max(int a, int b){
     return a > b ? a : b;
 }

 void construiesc(int st, int dr, int poz){
     if (st == dr){
         init[st] = poz;
         return ;
     }

     int x = (st+dr) / 2;

     construiesc(st, x, 2*poz);
     construiesc(x+1, dr, 2*poz+1);
 }
 void actualizez(int poz){
     for (; poz; poz /= 2){
         q[poz].sm = q[2*poz].sm + q[2*poz+1].sm;
         q[poz].x = max(q[2*poz].x, q[2*poz].sm + q[2*poz+1].x);
         q[poz].y = max(q[2*poz+1].y, q[2*poz+1].sm + q[2*poz].y);
         q[poz].rp = max(q[2*poz].rp, q[2*poz+1].rp);
         q[poz].rp = max(q[poz].rp, q[2*poz].y + q[2*poz+1].x);
     }
 }



 void interogare(int st, int dr, int poz){
     if (st >= p1 && dr <= p2){

         rsp = max(rsp, q[poz].rp);
         rsp = max(rsp, l2 + q[poz].x);
         l2 = max(q[poz].y, l2 + q[poz].sm);

         return ;
     }
     if (st > p2 || dr < p1 || st == dr)
         return ;

     int x = (st+dr) / 2;
     interogare(st, x, 2*poz);
     interogare(x+1, dr, 2*poz+1);
 }

 int main()
 {
    ifstream f("sequencequery.in");
     ofstream g("sequencequery.in");

     f>>n;
     construiesc(1, n, 1);

     for (i = 1; i <= n; i ++){
         f>>x;

         poz = init[i];
         q[poz].x = q[poz].y = q[poz].rp = q[poz].sm = x;

         actualizez(poz / 2);
     }
     f>>m;
     int op;
     for (i = 1; i <= m; i ++){
        f>>op>>p1>>p2;

         rsp = -1000000, l2 = -1000000;
         if (op==1)
         {p1++;p2++;
         interogare(1, n, 1);

         g<<rsp<<"\n";}
         else if (op==0)
           {p1++;
                 poz=init[p1];
            q[poz].x = q[poz].y = q[poz].rp = q[poz].sm = p2;

         actualizez(poz / 2); }

     }
       f.close();
       g.close();
     return 0;
 }