//
// Created by Vlad Nitu on 11.02.2023.
//

#include <bits/stdc++.h>

using namespace std;

#define NMAX (int)(100001)
#define INF (int)(1e9)
#define ll long long
#define mkp make_pair
#define mkt make_tuple
#define lsb(x) (x & -x)


int T, N, Q;
int lo[4 * NMAX + 1], hi[4 * NMAX + 1], mx[4 * NMAX + 1], delta[4 * NMAX + 1];

void build(int i, int a, int b) { // Initialise SegmentTree
    lo[i] = a;
    hi[i] = b;
    if (a == b)
        return;

    int mid = (a + b) / 2;
    build(2 * i, a, mid);
    build(2 * i + 1, mid + 1, b);
}

// `prop` and `update` -> template for SegmentTree that need to be modified depending on the task (min, max, sum, etc.)
int prop(int i) { // Lazy propagation of Segment Tree => push changes down to children
    delta[2 * i] += delta[i];
    delta[2 * i + 1] += delta[i];
    delta[i] = 0;
}

void update(int i) { // Aggregate update function
    mx[i] = max(mx[2 * i] + delta[2 * i], mx[2 * i + 1] + delta[2 * i + 1]);
}

void increment(int i, int a, int b, int val) {
    if (b < lo[i] || hi[i] < a) // Outside the range [a,b] I'm updating
        return;

    if (a <= lo[i] &&
        hi[i] <= b) { // [a,b] (interval I'm trying to cover) completely covers current node ([lo[i], hi[i]])
        // Completely covering the subtree
        delta[i] += val;
        return;
    }

    // Partial cover case

    prop(i); // Push change down to children before recursing

    increment(2 * i, a, b, val);
    increment(2 * i + 1, a, b, val);

    update(i); // Store aggregate maximum of the entire subtree
}

void increment(int a, int b, int val) { // UPDATE: Increment all values in range [a, b] by `val`
    increment(1, a, b, val);
}

int maximum(int i, int a, int b) {

    if (b < lo[i] || a > hi[i]) // Outside range
        return -1;

    if (a <= lo[i] && b >= hi[i]) // Entirely covering the node
        return mx[i] + delta[i];

    // Partial cover case

    prop(i);

    int maxLeft = maximum(2 * i, a, b);
    int maxRight = maximum(2 * i + 1, a, b);

    update(i);

    return max(maxLeft, maxRight);
}

int maximum(int a, int b) { // QUERY: Maximum element in range [a, b]
    return maximum(1, a, b);
}

int task, a, b, x;
int main() {

    freopen("arbint.in", "r", stdin);
    freopen("arbint.out", "w", stdout);

    cin >> N >> Q;

    build(1, 1, N);


    for (int i = 1; i <= N; ++i)
    {
        cin >> x;
        increment(i, i, x);
    }

    while (Q --) {
        cin >> task >> a >> b;

        if (task == 0) {
            cout << maximum(a, b) << '\n';
        }
        else
        {
            int cur_val = maximum(a, a);
            increment(a, a, -cur_val + b); // v[a] = b
        }

    }


    return 0;
}