#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 double db;

const LL LINF = 1e17;
const int LOG = 20;
const int N = 1 << 21;

struct SparseTable
{
	int n;
	VI lg;
	vector<vector<LL>> t;
	SparseTable(int _n): n(_n), lg(n + 1), t(LOG, vector<LL>(n))
	{
		lg[1] = 0;
		FOR(i, 2, n + 1)
			lg[i] = lg[i / 2] + 1;
	}
	void build(const vector<LL>& a)
	{
		t[0] = a;
		FOR(i, 1, LOG)
		{
			FOR(j, 0, n + 1 - (1 << i))
			{
				t[i][j] = min(t[i - 1][j], t[i - 1][j + (1 << (i - 1))]);
			}
		}
	}
	LL query(int l, int r)
	{
		int len = lg[r - l + 1];
		return min(t[len][l], t[len][r - (1 << len) + 1]);
	}
};

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n, q;
	cin >> n >> q;
	VI a(n);
	for (int& ai : a)
		cin >> ai;
	vector<LL> s(n + 1);
	FOR(i, 0, n)
		s[i + 1] = s[i] + a[i];
	SparseTable stmn(n + 1), stmx(n + 1);
	stmn.build(s);
	FOR(i, 0, n + 1)
		s[i] *= -1;
	stmx.build(s);
	FOR(i, 0, n + 1)
		s[i] *= -1;
	while (q--)
	{
		int ty;
		cin >> ty;
		if (ty == 1)
		{
			int l, r;
			cin >> l >> r;
			l--;
			LL sl = s[l], sr = s[r];
			LL mn = stmn.query(l, r), mx = -stmx.query(l, r);
			LL ans = abs(sr - sl);
			ans = max(ans, min(sl - mn, sr - mn));
			ans = max(ans, min(mx - sl, mx - sr));
			LL le = 0, ri = LINF;
			while (ri - le > 1)
			{
				LL mid = (le + ri) / 2;
				bool ok = false;
				if (sl < sr)
				{
					if (mid <= mx - sl && mid <= sr - mn)
					{
						int ll = l - 1, rr = r;
						while (rr - ll > 1)
						{
							int mm = (ll + rr) / 2;
							if (-stmx.query(l, mm) - sl >= mid)
								rr = mm;
							else
								ll = mm;
						}
						if (rr < r && sr - stmn.query(rr + 1, r) >= mid)
							ok = true;
					}
				}
				else
				{
					if (mid <= sl - mn && mid <= mx - sr)
					{
						int ll = l - 1, rr = r;
						while (rr - ll > 1)
						{
							int mm = (ll + rr) / 2;
							if (sl - stmn.query(l, mm) >= mid)
								rr = mm;
							else
								ll = mm;
						}
						if (rr < r && -stmx.query(rr + 1, r) - sr >= mid)
							ok = true;
					}
				}
				if (ok)
					le = mid;
				else
					ri = mid;
			}
			cout << max(ans, le) << "\n";
		}
		else
		{
			int x, v;
			cin >> x >> v;
			x--;
			assert(false);
			a[x] = v;
		}
	}
	cerr << (db)clock() / CLOCKS_PER_SEC << endl;
	return 0;
}