#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int N = 1e5 + 9,ROOT = 1,INF = 1e9 + 9;
int a[N];
struct seg_tree{
	struct node {
		int val,sum,lsum,rsum,change;
	} tree[N << 2];
	bool in_range(int l,int r,int now_l,int now_r){
		return l <= now_l && now_r <= r;
	}
	bool out_range(int l,int r,int now_l,int now_r){
		return now_r < l || now_l > r;
	}
	int len(int l,int r){
	    return r - l + 1;
	}
	void push_up(int root){
		int lchild = root * 2,rchild = root * 2 + 1;
		tree[root].sum = tree[lchild].sum + tree[rchild].sum;
		tree[root].val = max(max(tree[lchild].val,tree[rchild].val),tree[lchild].rsum + tree[rchild].lsum);
		tree[root].lsum = max(tree[lchild].lsum,tree[lchild].sum + tree[rchild].lsum);
		tree[root].rsum = max(tree[rchild].rsum,tree[rchild].sum + tree[lchild].rsum);
	}
	void make_tag(int Len,int root,int change){
		tree[root].change = change;
		tree[root].val = tree[root].sum = tree[root].lsum = tree[root].rsum = Len * change;
	}
	void push_down(int l,int r,int root){
	    int mid = (l + r) / 2,lchild = root * 2,rchild = root * 2 + 1;
		if(tree[root].change != INF){
			make_tag(len(l,mid),lchild,tree[root].change);
			make_tag(len(mid + 1,r),rchild,tree[root].change);
			tree[root].change = INF;
		}
	}
	void build(int l,int r,int root) {
		tree[root].change = INF;
		if(l == r) {
			tree[root].val = tree[root].sum = tree[root].lsum = tree[root].rsum = a[l];
			return;
		}
		int mid = (l + r) / 2,lchild = root * 2,rchild = root * 2 + 1;
		build(l,mid,lchild);
		build(mid + 1,r,rchild);
		push_up(root);
	}
	void update(int l,int r,int now_l,int now_r,int root,int change) {
		if(in_range(l,r,now_l,now_r))
			make_tag(len(l,r),root,change);
		else if(!out_range(l,r,now_l,now_r)){
			int mid = (now_l + now_r) / 2,lchild = root * 2,rchild = root * 2 + 1;
			push_down(now_l,now_r,root);
			update(l,r,mid + 1,now_r,rchild,change);
			update(l,r,now_l,mid,lchild,change);
			push_up(root);
		}
		return;
	}
	int getsum(int l, int r, int now_l, int now_r, int root) {
		int mid = (now_l + now_r) / 2,lchild = root * 2,rchild = root * 2 + 1;
		if(in_range(l,r,now_l,now_r))
			return tree[root].val;
		else if(!out_range(l,r,now_l,now_r)){
			push_down(now_l,now_r,root);
			return max(getsum(l,r,now_l,mid,lchild),getsum(l,r,mid + 1,now_r,rchild));
		}
		else
			return -INF;
	}
} seg;
int n,m;
int op,x,y,k;
signed main() {
	scanf("%lld%lld", &n, &m);
	for(int i = 1; i <= n; i++)
		scanf("%lld", &a[i]);
	seg.build(1,n,ROOT);
	for(int i = 1; i <= m; i++) {
		scanf("%lld%lld%lld", &op, &x, &y);
		if(op == 1){
			if(x > y)
				swap(x,y);
			printf("%lld\n",seg.getsum(x,y,1,n,ROOT));
		}
		else
			seg.update(x,x,1,n,ROOT,y);
	}
}