#include <bits/stdc++.h>
using namespace std;

#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define RFOR(i, a, b) for(int i = (a) - 1; i >= (b); i--)
#define SZ(a) int(a.size())
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define F first
#define S second

typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
typedef double db;

const LL LINF = 1e18;

struct SegTree
{
	vector<LL> lazy;
	vector<PLL> t;
	
	void init(int _n)
	{
		int n = 1;
		while(n < _n)
			n *= 2;
		t.assign(2 * n, MP(0, -1));
		lazy.assign(2 * n, 0);
	}
	void build(int v, int tl, int tr, const vector<LL>& vals)
	{
		if(tl + 1 == tr)
		{
			t[v] = MP(vals[tl], tl);
			return;
		}
		int tm = (tl + tr) / 2;
		build(2 * v + 1, tl, tm, vals);
		build(2 * v + 2, tm, tr, vals);
		
		t[v] = max(t[2 * v + 1], t[2 * v + 2]);
	}
	void push(int v, int tl, int tr)
	{
		t[v].F += lazy[v];
		if(tl + 1 != tr)
		{
			lazy[2 * v + 1] += lazy[v];
			lazy[2 * v + 2] += lazy[v];
		}
		lazy[v] = 0;
	}
	void upd(int v, int tl, int tr, int l, int r, int val)
	{
		push(v, tl, tr);
		if(r <= tl || tr <= l)
			return;
		if(l <= tl && tr <= r)
		{
			lazy[v] += val;
			push(v, tl, tr);
			return;
		}
		int tm = (tl + tr) / 2;
		upd(2 * v + 1, tl, tm, l, r, val);
		upd(2 * v + 2, tm, tr, l, r, val);
		
		t[v] = max(t[2 * v + 1], t[2 * v + 2]);
	}
	PLL query(int v, int tl, int tr, int l, int r)
	{
		push(v, tl, tr);
		if(r <= tl || tr <= l)
			return MP(-LINF, -1);
		if(l <= tl && tr <= r)
			return t[v];
		
		int tm = (tl + tr) / 2;
		return max(query(2 * v + 1, tl, tm, l, r),
				   query(2 * v + 2, tm, tr, l, r));
	}
};


int main()
{
	ios::sync_with_stdio(0); 
	cin.tie(0);
	
	int n, q;
	cin >> n >> q;
	
	VI a(n);
	vector<LL> pref(n + 1), rpref(n + 1);
	FOR(i, 0, n)
	{
		cin >> a[i];
	
		pref[i + 1] = pref[i] + a[i];
		rpref[i + 1] = -pref[i + 1];
	}
	SegTree Mx, Mn;
	
	Mx.init(n + 1);
	Mn.init(n + 1);
	
	Mx.build(0, 0, n + 1, pref);
	Mn.build(0, 0, n + 1, rpref);
	
	
	while(q--)
	{
		int t, l, r;
		cin >> t >> l >> r;
		if(t == 1)
		{
			l--;
			
			LL prefR = Mx.query(0, 0, n + 1, r, r + 1).F; 
			LL prefL = Mx.query(0, 0, n + 1, l, l + 1).F; 
			
			LL ans = abs(prefR - prefL);
					
			int pos1 = Mx.query(0, 0, n + 1, l, r + 1).S;
			LL prefPos1 = Mx.query(0, 0, n + 1, pos1, pos1 + 1).F;
			LL cur1 = min(abs(prefPos1 - prefL), abs(prefR - prefPos1));
			ans = max(ans, cur1);
		
			LL pos2 = Mn.query(0, 0, n + 1, l, r + 1).S;
			LL prefPos2 = Mx.query(0, 0, n + 1, pos2, pos2 + 1).F;
			LL cur2 = min(abs(prefPos2 - prefL), abs(prefR - prefPos2));
			ans = max(ans, cur2);
			
			if(pos1 < pos2)
			{
				LL cur = min(min(prefPos1 - prefL, prefPos2 - prefPos1), prefR - prefPos2);
				ans = max(ans, cur);
			}
			else
			{
				LL cur = min(min(prefPos2 - prefL, prefPos1 - prefPos2), prefR - prefPos1);
				ans = max(ans, cur);
			}
			
				
			
			cout << ans << "\n";
		}
		else
		{
			int d = r - a[l - 1];
			a[l - 1] = r;
			
			
			Mx.upd(0, 0, n + 1, l, n + 1, d);
			Mn.upd(0, 0, n + 1, l, n + 1, -d);
		}
	}
	
	
	return 0;
}