#include <iostream>
#include <fstream>
#include <math.h>

using namespace std;
ifstream f("arbint.in");
ofstream g("arbint.out");
#define cout g
int *t,n,m;
int *gyt;
int gytertek(int i);
int elsomuvelet(int a,int b){///osszeg a-tol b-ig
    int elsogyok=gytertek(a),masodikgyok=gytertek(b);
    int max=-1;
    for(int i=elsogyok+1;i<masodikgyok and i <=sqrt(n);i++){
        if(gyt[i]>max){
            max=gyt[i];
        }
    }
    for(int i=a;gytertek(i)==elsogyok and i<=b and i<=n;i++){
        if(t[i]>max)max=t[i];
    }
    for(int i=b;gytertek(i)==masodikgyok and i>=a and i>=1;i--){
        if(t[i]>max)max=t[i];
    }
    return max;

}
void masodikmuvelet(int a,int b){///beszuras t[a]=b
    t[a]=b;
    int elsogyok=gytertek(a);
    int max=-1;
    for(int i=a;gytertek(i)==elsogyok and i>=1;i--){
        if(t[i]>max){
            max=t[i];
        }
    }
    for(int i=a;gytertek(i)==elsogyok and i<=n;i++){
        if(t[i]>max){
            max=t[i];
        }
    }
    gyt[elsogyok]=max;
}
int *ujt(int n){
    int*t=new int[n+2];
    for(int i=0;i<=n+1;i++){
        t[i]=0;
    }
    return t;
}

int gytertek(int i){
    return i/sqrt(n);
}

int main()
{
    f>>n>>m;
    t=ujt(n);
    gyt=ujt(sqrt(n));
    for(int i=1;i<=n;i++){
        f>>t[i];
        gyt[gytertek(i)]+=t[i];
    }
    /*for(int i=0;i<=sqrt(n);i++){
        cout<<gyt[i]<<' ';
    }*/
    bool ok=0;
    for(int i=0;i<m;i++){
        int a,b,muvelet;
        f>>muvelet>>a>>b;
        if(muvelet==0){
            if(ok)cout<<endl;
            ok=1;
            cout<<elsomuvelet(a,b);
        }else{
            masodikmuvelet(a,b);
        }
    }

}