#include <bits/stdc++.h> using namespace std; const int N = 2e5 + 5, ND = N << 2, M = 45 + 5; //bool t1; int n, Q, a[N], k = 30, tmp[M << 2]; struct node { int len, a[M]; } res; void Merge(node &dst, node t1, node t2) { int n1 = t1.len, n2 = t2.len; int pos = 0; int i = 1, j = 1; while (i <= n1 || j <= n2) { if (j > n2 || (i <= n1 && t1.a[i] >= t2.a[j])) tmp[++pos] = t1.a[i++]; else tmp[++pos] = t2.a[j++]; } dst.len = min(n1 + n2, k); for (int i = 1; i <= dst.len; i++) dst.a[i] = tmp[i]; } #define lson u + u #define rson u + u + 1 struct segtree { node t[ND]; void pushup(int u) { Merge(t[u], t[lson], t[rson]); } void build(int u, int l, int r) { if (l == r) { t[u].len = 1; t[u].a[1] = a[l]; return; } int mid = (l + r) >> 1; build(lson, l, mid); build(rson, mid + 1, r); pushup(u); } void update(int u, int l, int r, int it, int x) { if (l == r) { t[u].a[1] = x; return; } int mid = (l + r) >> 1; if (it <= mid) update(lson, l, mid, it, x); else update(rson, mid + 1, r, it, x); pushup(u); } void query(int u, int l, int r, int L, int R) { if (L <= l && r <= R) { Merge(res, res, t[u]); return; } int mid = (l + r) >> 1; if (L <= mid) query(lson, l, mid, L, R); if (mid + 1 <= R) query(rson, mid + 1, r, L, R); } } t; //bool t2; int main() { // freopen("triangle.in", "r", stdin); // freopen("triangle.out", "w", stdout); cin >> n >> Q; for (int i = 1; i <= n; i++) scanf("%d", a + i); t.build(1, 1, n); int op, x, y; while (Q--) { scanf("%d%d%d", &op, &x, &y); if (op == 0) t.update(1, 1, n, x, y); else { res.len = 0; t.query(1, 1, n, x, y); int i; for (i = 1; i + 2 <= res.len; i++) { if (res.a[i] < res.a[i + 1] + res.a[i + 2]) break; } printf("%d\n", i + 2 > res.len ? 0 : res.a[i] + res.a[i + 1] + res.a[i + 2]); } } // cout << (&t2 - &t1) / 1024 / 1024 << endl; return 0; }