#include <iostream>

 #include <vector>

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #include <map>

 #include <set>

 #include <string>

 #include <queue>

 using namespace std;

 #define pb(x) push_back(x)

 #define ll long long

 #define mk(x, y) make_pair(x, y)

 #define lson l, m, rt<<1

 #define mem(a) memset(a, 0, sizeof(a))

 #define rson m+1, r, rt<<1|1

 #define mem1(a) memset(a, -1, sizeof(a))

 #define mem2(a) memset(a, 0x3f, sizeof(a))

 #define rep(i, a, n) for(int i = a; i<n; i++)

 #define ull unsigned long long

 typedef pair<int, int> pll;

 const double eps = 1e-;

 const int mod = 1e9+;

 const int inf = ;

 const int maxn = 5e4+;

 int sum[maxn<<], suf_max[maxn<<], pre_max[maxn<<], maxx[maxn<<];

 void pushUp(int rt) {

     sum[rt] = sum[rt<<] + sum[rt<<|];

     suf_max[rt] = max(suf_max[rt<<|], suf_max[rt<<]+sum[rt<<|]);

     pre_max[rt] = max(pre_max[rt<<], pre_max[rt<<|]+sum[rt<<]);

     maxx[rt] = max(maxx[rt<<], maxx[rt<<|]);

     maxx[rt] = max(maxx[rt], suf_max[rt<<]+pre_max[rt<<|]);

 }

 void build(int l, int r, int rt) {

     if(l == r) {

         scanf("%d", &maxx[rt]);

         sum[rt] = pre_max[rt] = suf_max[rt] = maxx[rt];

         return ;

     }

     int m = l+r>>;

     build(lson);

     build(rson);

     pushUp(rt);

 }

 void update(int p, int val, int l, int r, int rt) {

     if(l == r) {

         sum[rt] = pre_max[rt] = suf_max[rt] = maxx[rt] = val;

         return ;

     }

     int m = l+r>>;

     if(p<=m)

         update(p, val, lson);

     else

         update(p, val, rson);

     pushUp(rt);

 }

 int query_sum(int L, int R, int l, int r, int rt) {

     if(L<=l&&R>=r) {

         return sum[rt];

     }

     int m = l+r>>, ret = ;

     if(L<=m)

         ret += query_sum(L, R, lson);

     if(R>m)

         ret += query_sum(L, R, rson);

     return ret;

 }

 int query_suf(int L, int R, int l, int r, int rt) {

     if(L<=l&&R>=r) {

         return suf_max[rt];

     }

     int m = l+r>>;

     if(R<=m)

         return query_suf(L, R, lson);

     if(L>m)

         return query_suf(L, R, rson);

     return max(query_suf(L, m, lson)+query_sum(m+, R, rson), query_suf(m+, R, rson));

 }

 int query_pre(int L, int R, int l, int r, int rt) {

     if(L<=l&&R>=r) {

         return pre_max[rt];

     }

     int m = l+r>>;

     if(R<=m)

         return query_pre(L, R, lson);

     if(L>m)

         return query_pre(L, R, rson);

     return max(query_pre(L, m, lson), query_pre(m+, R, rson)+query_sum(L, m, lson));

 }

 int query(int L, int R, int l, int r, int rt) {

     if(L<=l&&R>=r) {

         return maxx[rt];

     }

     int m = l+r>>;

     if(R<=m)

         return query(L, R, lson);

     if(L>m)

         return query(L, R, rson);

     return max(max(query(L, m, lson), query(m+, R, rson)), query_pre(m+, R, rson)+query_suf(L, m, lson));

 }

 int main()

 {

     int n, q, x, y, sign;

     scanf("%d", &n);

     build(, n, );

     scanf("%d", &q);

     while(q--) {

         scanf("%d%d%d", &sign, &x, &y);

         if(sign)

             printf("%d\n", query(x, y, , n, ));

         else

             update(x, y, , n, );

     }

     return ;

 }