#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 2e5 + 9; #define ls(u) (u << 1) #define rs(u) (u << 1 | 1) struct node { int a[31], len; }; int n, q, a[N]; struct seg { node t[N << 2]; node pu(node x, node y) { node res; res.len = min(30, x.len + y.len); int px = 1, py = 1, p = 1; while (p <= res.len) { if (px <= x.len && (py > y.len || x.a[px] > y.a[py])) { res.a[p++] = x.a[px++]; } else { res.a[p++] = y.a[py++]; } } return res; } 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(ls(u), l, mid), build(rs(u), mid + 1, r); t[u] = pu(t[ls(u)], t[rs(u)]); } void upd(int u, int l, int r, int x, int v) { if (l == r) { t[u].a[1] = v; return; } int mid = (l + r) >> 1; if (x <= mid) upd(ls(u), l, mid, x, v); else upd(rs(u), mid + 1, r, x, v); t[u] = pu(t[ls(u)], t[rs(u)]); } node qry(int u, int l, int r, int x, int y) { if (x <= l && r <= y) return t[u]; int mid = (l + r) >> 1; if (y <= mid) return qry(ls(u), l, mid, x, y); else if (x > mid) return qry(rs(u), mid + 1, r, x, y); else return pu(qry(ls(u), l, mid, x, y), qry(rs(u), mid + 1, r, x, y)); } } T; signed main() { scanf("%d%d", &n, &q); for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); } T.build(1, 1, n); while (q--) { int op, x, y; scanf("%d%d%d", &op, &x, &y); if (!op) T.upd(1, 1, n, x, y); else { node u = T.qry(1, 1, n, x, y); int fl = 0; for (int i = 1; i <= u.len - 2; i++) { if (u.a[i] < u.a[i + 1] + u.a[i + 2]) { printf("%d\n", u.a[i] + u.a[i + 1] + u.a[i + 2]); fl = 1; break; } } if (!fl) printf("0\n"); } } return 0; }