#include <bits/stdc++.h>
using namespace std;

using ll = long long;
static const ll NEG = -(1LL << 60);

struct node {
    ll dp[2][2];
};

int n, q;
vector<ll> a;
vector<node> st;
int sz;

node make_leaf(ll x) {
    node t;
    for (int i = 0; i < 2; ++i)
        for (int j = 0; j < 2; ++j)
            t.dp[i][j] = NEG;

    // dp[l][r]:
    // l = trạng thái chọn ở đầu đoạn
    // r = trạng thái chọn ở cuối đoạn
    // với đoạn 1 phần tử, 4 trạng thái cơ bản
    t.dp[0][0] = 0;   // không chọn gì
    t.dp[1][1] = x;   // chọn phần tử này
    return t;
}

node merge_node(const node &L, const node &R) {
    node res;
    for (int i = 0; i < 2; ++i)
        for (int j = 0; j < 2; ++j)
            res.dp[i][j] = NEG;

    for (int l1 = 0; l1 < 2; ++l1) {
        for (int r1 = 0; r1 < 2; ++r1) {
            if (L.dp[l1][r1] == NEG) continue;
            for (int l2 = 0; l2 < 2; ++l2) {
                for (int r2 = 0; r2 < 2; ++r2) {
                    if (R.dp[l2][r2] == NEG) continue;

                    // không được chọn cả cuối trái và đầu phải
                    if (r1 == 1 && l2 == 1) continue;

                    int nl = l1;
                    int nr = r2;
                    res.dp[nl][nr] = max(res.dp[nl][nr], L.dp[l1][r1] + R.dp[l2][r2]);
                }
            }
        }
    }
    return res;
}

void build() {
    for (int i = sz - 1; i >= 1; --i) {
        st[i] = merge_node(st[i << 1], st[i << 1 | 1]);
    }
}

void update(int pos, ll val) {
    int p = sz + pos - 1;
    st[p] = make_leaf(val);
    for (p >>= 1; p; p >>= 1) {
        st[p] = merge_node(st[p << 1], st[p << 1 | 1]);
    }
}

node query(int l, int r) {
    node left, right;
    bool hasLeft = false, hasRight = false;

    for (int i = 0; i < 2; ++i)
        for (int j = 0; j < 2; ++j)
            left.dp[i][j] = right.dp[i][j] = NEG;

    l = l + sz - 1;
    r = r + sz - 1;

    while (l <= r) {
        if (l & 1) {
            if (!hasLeft) {
                left = st[l];
                hasLeft = true;
            } else {
                left = merge_node(left, st[l]);
            }
            ++l;
        }
        if (!(r & 1)) {
            if (!hasRight) {
                right = st[r];
                hasRight = true;
            } else {
                right = merge_node(st[r], right);
            }
            --r;
        }
        l >>= 1;
        r >>= 1;
    }

    if (!hasLeft) return right;
    if (!hasRight) return left;
    return merge_node(left, right);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> q;
    a.assign(n + 1, 0);
    for (int i = 1; i <= n; ++i) cin >> a[i];

    sz = 1;
    while (sz < n) sz <<= 1;
    st.assign(sz << 1, make_leaf(NEG));

    for (int i = 1; i <= n; ++i) st[sz + i - 1] = make_leaf(a[i]);
    for (int i = n + 1; i <= sz; ++i) st[sz + i - 1] = make_leaf(NEG);

    build();

    while (q--) {
        int type;
        cin >> type;
        if (type == 1) {
            int x;
            ll y;
            cin >> x >> y;
            a[x] = y;
            update(x, y);
        } else {
            int l, r;
            cin >> l >> r;
            node ans = query(l, r);
            ll best = NEG;
            for (int i = 0; i < 2; ++i)
                for (int j = 0; j < 2; ++j)
                    best = max(best, ans.dp[i][j]);
            cout << best << '\n';
        }
    }

    return 0;
}