#include <fstream>
#include <climits>
using namespace std;
ifstream fin("arbint.in");
ofstream fout("arbint.out");
const int NMax = 100005;
const int INF = INT_MIN;

int n,m;
int A[NMax];

int Tree[4 * NMax];
int Lazy[4 * NMax];

void Read(){
    fin >>n>>m;
    for(int i = 1; i <= n; i++){
        fin >> A[i];
    }
}

//void sum(int a, int b, int& res){
//    res = a + b;
//}

void build(int node, int L, int R){

    if(L == R){
        Tree[node] = A[L];
        return;
    }
    build(2 * node, L, (L + R) / 2);
    build(2 * node + 1, (L + R) / 2 + 1, R);
    Tree[node] = max(Tree[2 * node], Tree[2 * node + 1]);
}

void update(int node, int L, int R, int pos, int newVal){
    if(L == R && L == pos){
        Tree[node] = newVal;
        return;
    }
    int mid = (L + R) / 2;
    if(pos <= mid){
        update(2 * node, L, (L + R) / 2, pos, newVal);
    }
    else{
        update(2 * node + 1, (L + R) / 2 + 1, R, pos, newVal);
    }
    Tree[node] = max(Tree[node * 2], Tree[node * 2 + 1]);
}
void propagate(int node, int L, int R){

    Tree[node] += Lazy[node];
    if(L != R){
        Lazy[2 * node] += Lazy[node];
        Lazy[2 * node + 1] += Lazy[node];
    }
    Lazy[node] = 0;

}
int query(int node, int L, int R, int x, int y){

    propagate(node, L, R);
    if(R < x || L > y)
        return -INF;
    if(L >= x && R <= y){
        return Tree[node];
    }
    int resLeft = query(node * 2, L, (L + R) / 2, x, y);
    int resRight = query(node * 2 + 1, (L + R) / 2 + 1, R, x, y);
    return max(resLeft, resRight);

}



void rangeUpdate(int node, int L, int R, int x, int y, int addedValue){

    propagate(node, L, R);

    if(L > y || R < x)
        return;

    if(L >= x && R <= y){
        Tree[node] += addedValue;
        if(L != R){
            Lazy[node * 2] += addedValue;
            Lazy[node * 2 + 1] += addedValue;
        }
        return;
    }

    rangeUpdate(node * 2, L, (L + R) / 2, x, y, addedValue);
    rangeUpdate(node * 2 + 1, (L + R ) / 2 + 1, R, x, y, addedValue);
    Tree[node] = max(Tree[node * 2], Tree[node * 2 + 1]);

}


int main()
{
    int pos,val,c,a,b;
    Read();
    build(1, 1, n);

    for(int i=1;i<=n;i++)
    {
        fin>>c>>a>>b;
        if(c==0)
          fout<<query(1, 1, n, a, b)<<"\n";
        else
          update(1, 1, n, a, b);
    }

    return 0;
}