#include<bits/stdc++.h>
using namespace std;
const int N = 5e5 + 20;

struct Node{
    int l, r;
    int tsum; //最大子段和
    int lsum; //最大前缀和
    int rsum; //最大后缀和
    int sum; //区间和
} tr[N << 2];
int w[N];

void pushup(Node &root, Node &l, Node &r)
{
    root.sum = l.sum + r.sum;
    root.lsum = max(l.lsum, l.sum + r.lsum);
    root.rsum = max(r.rsum, r.sum + l.rsum);
    root.tsum = max(max(l.tsum, r.tsum), l.rsum + r.lsum);
}

void pushup(int u)
{
    pushup(tr[u], tr[u << 1], tr[u << 1 | 1]);
}

void build(int u, int l, int r)
{
    if(l == r) tr[u] = {l, r, w[l], w[l], w[l], w[l]};
    else
    {
        tr[u] = {l, r};
        int mid = l + r >> 1;
        build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
        pushup(u);
    }
}

void modify(int u, int x, int v)
{
    if(tr[u].l == x && tr[u].r == x) tr[u] = {x, x, v, v, v, v};
    else
    {
        int mid = tr[u].l + tr[u].r >> 1;
        if(x <= mid) modify(u << 1, x, v);
        else modify(u << 1 | 1, x, v);
        pushup(u);
    }
}

Node query(int u, int l, int r)
{
    if(l <= tr[u].l && tr[u].r <= r) return tr[u];
    else
    {
        int mid = tr[u].l + tr[u].r >> 1;
        if(r <= mid) return query(u << 1, l, r);
        else if(l > mid) return query(u << 1 | 1, l, r);
        else
        {
            Node left = query(u << 1, l, r);
            Node right = query(u << 1 | 1, l, r);
            Node res;
            pushup(res, left, right);
            return res;
        }
    }
}

int main()
{
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> w[i];
    build(1, 1, n);
    while(m --)
    {
        int op, x, y;
        cin >> op >> x >> y;
        if(op == 1)
        {
            if(x > y) swap(x, y);
            cout << query(1, x, y).tsum << endl;
        }
        else modify(1, x, y);
    }
    return 0;
}