#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 500005;
const int INF = 0x3f3f3f3f;

struct Node {
    int sum, lmax, rmax, dat;
    Node() : sum(0), lmax(-INF), rmax(-INF), dat(-INF) {}
    Node(int v) : sum(v), lmax(v), rmax(v), dat(v) {}
} tr[MAXN << 2];

Node merge(const Node &ls, const Node &rs) {
    Node res;
    res.sum = ls.sum + rs.sum;
    res.lmax = max(ls.lmax, ls.sum + rs.lmax);
    res.rmax = max(rs.rmax, rs.sum + ls.rmax);
    res.dat = max({ls.dat, rs.dat, ls.rmax + rs.lmax});
    return res;
}

int a[MAXN];

void build(int u, int l, int r) {
    if (l == r) {
        tr[u] = Node(a[l]);
        return;
    }
    int mid = (l + r) / 2;
    build(u << 1, l, mid);
    build(u << 1 | 1, mid + 1, r);
    tr[u] = merge(tr[u << 1], tr[u << 1 | 1]);
}

void update(int u, int l, int r, int pos, int val) {
    if (l == r) {
        tr[u] = Node(val);
        return;
    }
    int mid = (l + r) / 2;
    if (pos <= mid) update(u << 1, l, mid, pos, val);
    else update(u << 1 | 1, mid + 1, r, pos, val);
    tr[u] = merge(tr[u << 1], tr[u << 1 | 1]);
}

Node query(int u, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) {
        return tr[u];
    }
    int mid = (l + r) / 2;
    if (qr <= mid) return query(u << 1, l, mid, ql, qr);
    if (ql > mid) return query(u << 1 | 1, mid + 1, r, ql, qr);
    Node left = query(u << 1, l, mid, ql, qr);
    Node right = query(u << 1 | 1, mid + 1, r, ql, qr);
    return merge(left, right);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }
    build(1, 1, n);
    while (m--) {
        int k, x, y;
        cin >> k >> x >> y;
        if (k == 1) {
            if (x > y) swap(x, y);
            Node ans = query(1, 1, n, x, y);
            cout << ans.dat << '\n';
        } else {
            update(1, 1, n, x, y);
        }
    }
    return 0;
}