#include <bits/stdc++.h>
#define debug(x) cout << #x << " = " << x << endl;
using namespace std;
typedef long long LL;
const int maxn = 5e5 + 10;
const int inf = 0x3f3f3f3f;
const double eps = 1e-6, pi = acos(-1.0);
int n, m;
LL arr[maxn];
struct Tree{
int l, r;
LL maxv, lsum, rsum, sum;
}t[maxn<<2];
inline LL max(LL a, LL b, LL c){
return max(a, max(b, c));
}
inline void pushup(int cur){
t[cur].sum = t[cur<<1].sum + t[cur<<1|1].sum;
t[cur].lsum = max(t[cur<<1].lsum, t[cur<<1].sum + t[cur<<1|1].lsum);
t[cur].rsum = max(t[cur<<1|1].rsum, t[cur<<1].rsum + t[cur<<1|1].sum);
t[cur].maxv = max(t[cur<<1].maxv, t[cur<<1|1].maxv, t[cur<<1].rsum + t[cur<<1|1].lsum);
}
void build(int l, int r, int cur){
t[cur].l = l; t[cur].r = r;
t[cur].maxv = t[cur].lsum = t[cur].rsum = -inf;
t[cur].sum = 0;
if(l == r){
t[cur].maxv = t[cur].lsum = t[cur].rsum = t[cur].sum = 1LL * arr[l];
return;
}
int mid = l + r >> 1;
build(l, mid, cur<<1);
build(mid + 1, r, cur<<1|1);
pushup(cur);
}
void change(int pos, int x, int cur){
if(t[cur].l == t[cur].r){
if(t[cur].l == pos) t[cur].maxv = t[cur].lsum = t[cur].rsum = t[cur].sum = x;
return;
}
int mid = t[cur].l + t[cur].r >> 1;
if(pos <= mid) change(pos, x, cur<<1);
else change(pos, x, cur<<1|1);
pushup(cur);
}
Tree query(int l , int r, int cur){
Tree a, b, c;
if(l <= t[cur].l && t[cur].r <= r){
return t[cur];
}
int mid = t[cur].l + t[cur].r >> 1;
a.sum = a.lsum = a.rsum = a.maxv = -inf - 1;
b.sum = b.lsum = b.rsum = b.maxv = -inf - 1;
c.lsum = c.rsum = c.maxv = -inf - 1; c.sum = 0;
if(l <= mid){
a = query(l, r, cur << 1);
c.sum += a.sum;
}
if(mid < r){
b = query(l, r, cur<<1|1);
c.sum += b.sum;
}
c.lsum = max(a.lsum, a.sum + b.lsum);
c.rsum = max(b.rsum, a.rsum + b.sum);
c.maxv = max(a.maxv, max(b.maxv, a.rsum + b.lsum));
return c;
}
int main()
{
scanf("%d %d", &n, &m);
for(int i = 1; i <= n; ++i){
scanf("%lld", &arr[i]);
}
build(1, n, 1);
while(m--){
int k, l, r;
scanf("%d %d %d", &k, &l, &r);
if(k == 1){
printf("%lld\n", query(min(l, r), max(l, r), 1).maxv);
}
else{
change(l, r, 1);
}
}
getchar(); getchar();
}