/* created by chjshen, date: 2023-05-15 08:18 */
#include <cstdio>
#include <iostream>
using namespace std;
const int N = 5E5 + 5;
int a[N];
struct SegmentTree
{
    int l, r;
    long long sum;    // [l, r] 区间和
    long long data;   // [l, r] 区间的最大连续子段和
    long long datal;  // [l, r] 区间中以l为起点的最大子段和
    long long datar;  // [l, r] 区间中以r为终点的最大子段和
} st[N * 4];
int n, m;
inline void calc(int p)
{
    st[p].sum = st[p << 1].sum + st[p * 2 + 1].sum;  // [l, r]的区间和由其左右子树组成
    st[p].datal = max(st[p * 2].datal, st[p * 2].sum + st[p * 2 + 1].datal);  //
    st[p].datar = max(st[p * 2 + 1].datar, st[p * 2 + 1].sum + st[p * 2].datar);
    st[p].data =
        max(max(st[p * 2].data, st[p * 2 + 1].data), st[p * 2].datar + st[p * 2 + 1].datal);
}
void buildTree(int p, int l, int r)
{
    st[p].l = l, st[p].r = r;  // 节点p代表区间[l, r]
    if (l == r)                // 叶结点
    {
        st[p].sum = st[p].data = st[p].datal = st[p].datar = a[l];
        return;
    }
    int mid = l + (r - l) / 2;
    buildTree(p << 1, l, mid);
    buildTree((p << 1) + 1, mid + 1, r);
    calc(p);
}
SegmentTree queryTree(int p, int l, int r)
{
    // 1. 完全包含在区间内
    if (st[p].l >= l && r >= st[p].r) return st[p];
    // 2. 不完全
    int mid = st[p].l + (st[p].r - st[p].l) / 2;
    SegmentTree a, b, ans;
    ans.sum = 0;
    a.sum = b.sum = a.data = b.data = a.datal = b.datal = a.datar = b.datar = -(1 << 30);
    // 左节点有重合
    if (l <= mid) a = queryTree(p * 2, l, r), ans.sum += a.sum;
    // 右节点有重合
    if (r > mid) b = queryTree(p * 2 + 1, l, r), ans.sum += b.sum;
    ans.data = max(max(a.data, b.data), a.datar + b.datal);
    ans.datal = max(a.datal, a.sum + b.datal);
    ans.datar = max(b.datar, b.sum + a.datar);
    if (l > mid) ans.datal = max(ans.datal, b.datal);
    if (r <= mid) ans.datar = max(ans.datar, a.datar);
    return ans;
}
void updateTree(int p, int x, int y)
{
    if (st[p].l == st[p].r)
    {
        st[p].sum = st[p].data = st[p].datal = st[p].datar = y;
        return;
    }
    int mid = st[p].l + (st[p].r - st[p].l) / 2;
    if (x <= mid)
        updateTree(p * 2, x, y);
    else
        updateTree(p * 2 + 1, x, y);
    calc(p);
}
void handle(int k, int l, int r)
{
    if (k == 2)  // 修改
        updateTree(1, l, r);
    if (k == 1)  // 查询
    {
        if (l > r) swap(l, r);
        printf("%lld\n", queryTree(1, l, r).data);
    }
}
void initInput(void)
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    buildTree(1, 1, n);
    while (m--)
    {
        int k, l, r;
        scanf("%d%d%d", &k, &l, &r);
        handle(k, l, r);
    }
}
int main(void)
{
    initInput();
    return 0;
}