// implementam arbint cu lazy update (adunam o valoare pe interval la update)

#include <bits/stdc++.h>

using namespace std;

const int DIM = 100005;

int v[DIM];

struct NodAint {
    int max;
    int lazy;
};

NodAint aint[4 * DIM];

void build(int node, int left, int right) {
    if (left == right) {  // frunza
        aint[node].max =
            v[left];  // maximul pe intervalul [left, left] este v[left]
        aint[node].lazy = 0;
        return;
    }

    int mid = (left + right) / 2;
    build(2 * node, left, mid);           // recursiv pt fiul stang
    build(2 * node + 1, mid + 1, right);  // recursiv pt fiul drept
    aint[node].max =
        max(aint[2 * node].max,
            aint[2 * node + 1]
                .max);  // determinam maximul din intervalul [left, right]
}

void push_lazy(int node) {
    if (aint[node].lazy == 0) return;
    aint[2 * node].max += aint[node].lazy;  // push lazy fiul stang
    aint[2 * node].lazy += aint[node].lazy;
    aint[2 * node + 1].max += aint[node].lazy;  // push lazy fiul drept
    aint[2 * node + 1].lazy += aint[node].lazy;
    aint[node].lazy = 0;
}

void update(int node, int left, int right, int uLeft, int uRight, int val) {
    // updatam intervalul [uLeft, uRight] cu +=val

    if (uLeft <= left && right <= uRight) {  // left == pos
        aint[node].max += val;
        aint[node].lazy += val;
        return;
    }

    push_lazy(node);

    int mid = (left + right) / 2;
    if (uLeft <=
        mid)  // pozitia care trebuie actualizata este in jumatatea stanga
        update(2 * node, left, mid, uLeft, uRight, val);
    if (uRight > mid) update(2 * node + 1, mid + 1, right, uLeft, uRight, val);
    aint[node].max =
        max(aint[2 * node].max,
            aint[2 * node + 1]
                .max);  // actualizam maximul din intervalul [left, right]
}

int query(int node, int left, int right, int qLeft, int qRight) {
    // vrem sa determinam minimul din intervalul [qLeft, qRight]

    if (qLeft <= left &&
        right <=
            qRight) {  // intervalul curent este inclus in intervalul de query
        return aint[node].max;
    }

    push_lazy(node);

    int mid = (left + right) / 2;
    int res = -1000000000;
    if (qLeft <=
        mid)  // jumatatea stanga contine valori din intervalul de query
        res = max(res, query(2 * node, left, mid, qLeft, qRight));
    if (qRight >
        mid)  // jumatatea dreapta contine valori din intervalul de query
        res = max(res, query(2 * node + 1, mid + 1, right, qLeft, qRight));

    return res;
}

int main() {
    ifstream cin("arbint.in");
    ofstream cout("arbint.out");

    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) cin >> v[i];

    build(1, 1, n);  // construim arborele de intervale pentru v

    for (int i = 1; i <= m; ++i) {
        int op, a, b;
        cin >> op >> a >> b;

        if (op == 0)
            cout << query(1, 1, n, a, b) << "\n";
        else {
            update(1, 1, n, a, a, b - v[a]);
            v[a] = b;
        }
    }

    return 0;
}