#include <cstdio>
#include <cstring>
#include <climits>
#include <algorithm>
const int MAXN = 500000;
const int MAXM = 100000;
struct SegmentTree {
    struct Node {
        Node *lc, *rc;
        int l, r, val;
        int sum, lsum, rsum, maxSum;
        Node() {}
        Node(Node *lc, Node *rc, int l, int r) : lc(lc), rc(rc), l(l), r(r) {}
        void update() {
            sum = val;
            if (lc) sum += lc->sum;
            if (rc) sum += rc->sum;
            lsum = rsum = sum;
            if (lc) {
                lsum = std::max(lsum, lc->lsum);
                if (rc) lsum = std::max(lsum, lc->sum + rc->lsum);
            }
            if (rc) {
                rsum = std::max(rsum, rc->rsum);
                if (lc) rsum = std::max(rsum, rc->sum + lc->rsum);
            }
            maxSum = sum;
            maxSum = std::max(maxSum, lsum);
            maxSum = std::max(maxSum, rsum);
            if (lc) maxSum = std::max(maxSum, lc->maxSum);
            if (rc) maxSum = std::max(maxSum, rc->maxSum);
            if (lc && rc) maxSum = std::max(maxSum, lc->rsum + rc->lsum);
        }
        void query(int l, int r, int &sum, int &lsum, int &rsum, int &maxSum) {
            if (this->l > r || this->r < l) return;
            else if (this->l >= l && this->r <= r) {
                sum = this->sum;
                lsum = this->lsum;
                rsum = this->rsum;
                maxSum = this->maxSum;
            } else {
                int mid = (this->l + this->r) >> 1;
                if (r <= mid) return lc->query(l, r, sum, lsum, rsum, maxSum);
                if (l >= mid + 1) return rc->query(l, r, sum, lsum, rsum, maxSum);
                else {
                    int suml, lsuml, rsuml, maxSuml;
                    int sumr, lsumr, rsumr, maxSumr;
                    lc->query(l, r, suml, lsuml, rsuml, maxSuml);
                    rc->query(l, r, sumr, lsumr, rsumr, maxSumr);
                    maxSum = sum = suml + sumr;
                    lsum = std::max(lsuml, suml + lsumr);
                    rsum = std::max(rsumr, sumr + rsuml);
                    maxSum = std::max(maxSum, maxSuml);
                    maxSum = std::max(maxSum, maxSumr);
                    maxSum = std::max(maxSum, rsuml + lsumr);
                }
            }
        }
        void modify(int pos, int val) {
            if (this->l > pos || this->r < pos) return;
            else if (this->l == pos && this->r == pos) this->val = val, update();
            else {
                if (lc) lc->modify(pos, val);
                if (rc) rc->modify(pos, val);
                update();
            }
        }
    } *root;
    SegmentTree(int l, int r) {
        root = build(l, r);
    }
    Node *build(int l, int r) {
        if (l > r) return NULL;
        else if (l == r) return new Node(NULL, NULL, l, r);
        else {
            int mid = (l + r) >> 1;
            return new Node(build(l, mid), build(mid + 1, r), l, r);
        }
    }
    void modify(int pos, int val) {
        root->modify(pos, val);
    }
    int query(int l, int r) {
        int sum, lsum, rsum, maxSum;
        root->query(l, r, sum, lsum, rsum, maxSum);
        return maxSum;
    }
} *segt;
int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    segt = new SegmentTree(1, n);
    for (int i = 1; i <= n; i++) {
        int x;
        scanf("%d", &x);
        segt->modify(i, x);
    }
    for (int i = 0; i < m; i++) {
        int k;
        scanf("%d", &k);
        if (k == 1) {
            int l, r;
            scanf("%d %d", &l, &r);
            if (l > r) std::swap(l, r);
            printf("%d\n", segt->query(l, r));
        } else {
            int pos, val;
            scanf("%d %d", &pos, &val);
            segt->modify(pos, val);
        }
    }
    return 0;
}