#include <bits/stdc++.h>
#define int long long

using namespace std;

const int N = 5e5 + 10, INF = 1e18;

int Park, Operation;
int Points[N];
struct Segment
{
	int L, R;
	int Sum, Max;
	int Max_L, Max_R;
}Tree[N * 4];
struct Result
{
	int Sum;
	int Max, Max_L, Max_R;
};

Result Get_Max(Result A, Result B)
{
	int T0 = A.Sum + B.Sum;
	int T1 = max(max(A.Max, B.Max), A.Max_R + B.Max_L);
	int T2 = max(A.Max_L, A.Sum + B.Max_L);
	int T3 = max(B.Max_R, A.Max_R + B.Sum);

	return {T0, T1, T2, T3};
}

void Pushup(int u)
{
	Tree[u].Sum = Tree[u << 1].Sum + Tree[u << 1 | 1].Sum;
	bool Flag1 = (Tree[u << 1].Max_R < 0), Flag2 = (Tree[u << 1 | 1].Max_L < 0);
	if ((Flag1 && Flag2) || (Flag1 | Flag2)) Tree[u].Max = max(Tree[u << 1].Max_L, Tree[u << 1 | 1].Max_R);
	else Tree[u].Max = Tree[u << 1].Max_R + Tree[u << 1 | 1].Max_L;
	Tree[u].Max_L = max(Tree[u << 1].Sum + Tree[u << 1 | 1].Max_L, Tree[u << 1].Max_L);
	Tree[u].Max_R = max(Tree[u << 1].Max_R + Tree[u << 1 | 1].Sum, Tree[u << 1 | 1].Max_R);
}

void Build(int u, int l, int r)
{
	if (l == r)
		Tree[u] = {l, l, Points[l], Points[l], Points[l], Points[l]};
	else
	{
		Tree[u] = {l, r, 0, -INF, -INF, -INF};
		int mid = l + r >> 1;
		Build(u << 1, l, mid), Build(u << 1 | 1, mid + 1, r);
		Pushup(u);
	}
}

void Modify(int u, int Position, int Value)
{
	if (Tree[u].L == Tree[u].R && Tree[u].L == Position)
		Tree[u] = {Tree[u].L, Tree[u].R, Value, Value, Value, Value};
	else
	{
		int mid = Tree[u].L + Tree[u].R >> 1;
		if (mid >= Position) Modify(u << 1, Position, Value);
		else Modify(u << 1 | 1, Position, Value);
		Pushup(u);
	}
}

Result Query(int u, int l, int r)
{
	if (Tree[u].L >= l && Tree[u].R <= r)
		return {Tree[u].Max, Tree[u].Max_L, Tree[u].Max_R};
	
	int mid = Tree[u].L + Tree[u].R >> 1;
	Result Answer;
	if (mid >= l && mid < r)
		Answer = Get_Max(Query(u << 1, l, r), Query(u << 1 | 1, l, r));
	else if (mid >= l)
		Answer = Query(u << 1, l, r);
	else
		Answer = Query(u << 1 | 1, l, r);

	return Answer;
}

signed main()
{
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(0);

	cin >> Park >> Operation;

	for (int i = 1; i <= Park; i ++)
		cin >> Points[i];

	Build(1, 1, Park);

	while (Operation --)
	{
		int op, l, r;
		
		cin >> op >> l >> r;

		if (op == 1)
		{
			if (l > r) swap(l, r);
			cout << Query(1, l, r).Max << endl;
		}
		else
			Modify(1, l, r);
	}

	return 0;
}