#include<bits/stdc++.h>
#define lchild (root << 1)
#define rchild ((root << 1) + 1)
#define mid ((l + r) >> 1)
using namespace std;
const int N = 5e5 + 9,K = 3,INF = INT_MAX;
int n,m;
int a[N];
struct matrix{
	int A[K][K];
	matrix(){
		for(int i = 0;i < K;i++)
			for(int j = 0;j < K;j++)
				A[i][j] = -INF;
	}
};
matrix operator*(matrix a,matrix b){
    matrix c;
    for(int i = 0;i < K;i++){
        for(int j = 0;j < K;j++){
            int tmp = -INF;
            for(int k = 0;k < K;k++)
                tmp = max(tmp,a.A[i][k] + b.A[k][j]);
            c.A[i][j] = tmp;
        }
    }
    return c;
}

struct segment_tree{
	struct node{
		matrix val;
	}t[N << 2];
	void push_up(int root){
		t[root].val = t[lchild].val * t[rchild].val;
	}
	bool in_range(int l,int r,int L,int R){
		return L <= l && r <= R;
	}
	bool out_range(int l,int r,int L,int R){
		return l > R || r < L;
	}
	void build(int root,int l,int r){
		if(l == r){
			t[root].val.A[0][0] = a[l];    t[root].val.A[0][1] = -INF; t[root].val.A[0][2] = a[l];
			t[root].val.A[1][0] = a[l];    t[root].val.A[1][1] = 0;    t[root].val.A[1][2] = a[l];
			t[root].val.A[2][0] = -INF;    t[root].val.A[2][1] = -INF; t[root].val.A[2][2] = 0;
			return;
		}
		build(lchild,l,mid);
		build(rchild,mid + 1,r);
		push_up(root);
	}
	void update(int root,int l,int r,int k,int v){
		if(l == r){
			t[root].val.A[0][0] = v;    t[root].val.A[0][1] = -INF; t[root].val.A[0][2] = v;
			t[root].val.A[1][0] = v;    t[root].val.A[1][1] = 0;    t[root].val.A[1][2] = v;
			t[root].val.A[2][0] = -INF; t[root].val.A[2][1] = -INF; t[root].val.A[2][2] = 0;
			return;
		}
		if(k <= mid)
			update(lchild,l,mid,k,v);
		else
			update(rchild,mid + 1,r,k,v);
		push_up(root);
	}
	matrix query(int root,int l,int r,int L,int R){
		if(in_range(l,r,L,R)){
			return t[root].val;
		}
		matrix ret;
		if(L <= mid && R > mid)	
			return query(lchild,l,mid,L,R) * query(rchild,mid + 1,r,L,R);
		else if(L <= mid)
			return query(lchild,l,mid,L,R);
		else
			return query(rchild,mid + 1,r,L,R);
	}
} tree;
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin >> n >> m;
	for(int i = 1;i <= n;i++)
		cin >> a[i];
	tree.build(1,1,n);
	while(m--){
		int op,x,y;
		cin >> op >> x >> y;
		if(op == 1){
			if(x > y)
				swap(x,y);
			matrix ans = tree.query(1,1,n,x,y);
			cout << max(ans.A[1][0],ans.A[1][2]) << '\n';
		}
		else
			tree.update(1,1,n,x,y);
	}
	return 0;
}