#include <bits/stdc++.h>

using namespace std;

const int Nmax = 100010;

struct segTree {
    struct Node {
        int mx, lazy;
    };

    Node arb[4 * Nmax];
    int v[Nmax];

    void propag(int nod, int st, int dr)
    {
        arb[nod].mx += arb[nod].lazy;
        if (st < dr)
        {
            arb[nod * 2].lazy += arb[nod].lazy;
            arb[nod * 2 + 1].lazy += arb[nod].lazy;
        }
        arb[nod].lazy = 0;
    }

    void recalc(int nod)
    {
        arb[nod].mx = max(arb[nod * 2].mx, arb[nod * 2 + 1].mx);
    }

    void init(int nod, int st, int dr)
    {
        if (st == dr)
        {
            arb[nod].mx = v[st];
            arb[nod].lazy = 0;
            return;
        }
        int mid = (st + dr) / 2;
        init(nod * 2, st , mid);
        init(nod * 2 + 1, mid + 1, dr);
        recalc(nod);
        arb[nod].lazy = 0;
    }

    void update(int nod, int st, int dr, int left, int right, int x)
    {
        if(left <= st && dr <= right)
        {
            arb[nod].lazy += x;
            propag(nod, st, dr);
            return;
        }
        int mid = (st + dr) / 2;
        propag(nod, st, dr);
        if (left <= mid) update(nod * 2, st , mid, left ,right, x);
        else propag(nod * 2, st, mid);
        if (mid < right) update(nod * 2 + 1, mid + 1, dr, left, right, x);
        else propag(nod * 2 + 1, mid + 1, dr);
        recalc(nod);
    }

    int query(int nod, int st, int dr, int left, int right)
    {
        propag(nod, st, dr);
        if (left <= st && dr <= right) return arb[nod].mx;
        int mid = (st + dr) / 2, s = 0;
        if (left <= mid) s = query(nod * 2, st, mid, left, right);
        if (mid < right) s = max(s, query(nod * 2 + 1, mid + 1, dr, left, right));
        return s;
    }
};

segTree aint;

int main()
{
    freopen("arbint.in", "r", stdin);
    freopen("arbint.out", "w", stdout);
    int n, m, t, x, y;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) scanf("%d", &aint.v[i]);
    aint.init(1, 1, n);
    for (int i = 1; i <= m; ++i)
    {
        scanf("%d%d%d", &t, &x, &y);
        if (t) {aint.update(1, 1, n, x, x, y - aint.v[x]); aint.v[x] = y;}
        else printf("%d\n", aint.query(1, 1, n, x, y));
    }
    return 0;
}