#pragma GCC optimize("O3")
#include <bits/stdc++.h>

using namespace std;

vector<int> f(vector<int> a, vector<int> b) {
    vector<int> c(a.size() + b.size());
    merge(a.begin(), a.end(), b.begin(), b.end(), c.begin());
    reverse(c.begin(), c.end());
    if(c.size() > 50) {
        c.resize(50);
    }
    reverse(c.begin(), c.end());
    return c;
}

const int MAXN = 1e5 + 10;

int n, q;
vector<int> t[4 * MAXN];

void upd(int v, int l, int r, int pos, int x) {
    if(l == r) {
        t[v] = {x};
    }
    else {
        int m = (l + r) / 2;
        if(pos <= m) upd(2 * v, l, m, pos, x);
        else upd(2 * v + 1, m + 1, r, pos, x);
        t[v] = f(t[2 * v], t[2 * v + 1]);
    }
}

vector<int> get(int v, int l, int r, int L, int R) {
    if(r < L || R < l) return vector<int>(0);
    if(L <= l && r <= R) return t[v];
    int m = (l + r) / 2;
    return f(get(2 * v, l, m, L, R), get(2 * v + 1, m + 1, r, L, R));
}

long long get(int L, int R) {
    vector<int> v = get(1, 1, n, L, R);
    long long ans = 0;
    cerr << v.size() << endl;
    for(int i = 2; i < v.size(); i++) {
        if(v[i - 2] + v[i - 1] > v[i]) {
            ans = max(ans, (long long)(v[i] + v[i - 1]) +(long long)v[i - 2]);
        }
    }
    return ans;
}

int main() {
	#ifdef Fekete
		freopen("input.txt", "r", stdin);
		//freopen("output.txt", "w", stdout);
        freopen("debuger.txt", "w", stderr);
    #endif // Fekete


    scanf("%d%d", &n, &q);
    for(int i = 1; i <= n; i++) {
        int x;
        scanf("%d", &x);
        upd(1, 1, n, i, x);
    }

    while(q--) {
        int t, l, r;
        scanf("%d%d%d", &t, &l, &r);
        if(t == 1) {
            upd(1, 1, n, l, r);
        }
        else {
            cout << get(l, r) << "\n";
        }
    }
}