#include <fstream>

using namespace std;

const int N2MAX= 1024*128, INF= (1<<30);

ifstream in( "arbint.in" );
ofstream out( "arbint.out" );

int arb[N2MAX*2];

int query( int nod, int lq, int rq, int ln, int rn )
{
    if( rn < lq || ln > rq )
    {
        return -INF;
    }
    if( ln>= lq && rn <= rq )
    {
        return arb[nod];
    }

    if( max( arb[nod*2], arb[nod*2+1] )!=arb[nod] )
    {
        int aux= arb[nod]- max( arb[nod*2], arb[nod*2+1] );
        arb[nod*2]+= aux;
        arb[nod*2+1]+= aux;
    }

    int ans1= query(nod*2, lq, rq, ln, (ln+rn)/2 );
    int ans2= query(nod*2+1, lq, rq, (ln+rn)/2+1, rn );
    return max( ans1, ans2 );
}

void upd( int nod, int lq, int rq, int ln, int rn, int val )
{
    if( rn < lq || ln > rq )
    {
        return ;
    }
    if( ln >= lq && rn <= rq )
    {
        arb[nod]+= val;
        return ;
    }

    if( max( arb[nod*2], arb[nod*2+1] )!=arb[nod] )
    {
        int aux= arb[nod]- max( arb[nod*2], arb[nod*2+1] );
        arb[nod*2]+= aux;
        arb[nod*2+1]+= aux;
    }

    upd(nod*2, lq, rq, ln, (ln+rn)/2, val );
    upd(nod*2+1, lq, rq, (ln+rn)/2+1, rn, val );
    arb[nod]= max( arb[nod*2], arb[nod*2+1] );
}

int main(  )
{
    int N, M, N2= 1;
    in >> N >> M;

    while( N2<N )
    {
        N2*= 2;
    }

    for( int i= N2; i<=N2-1+N; ++i )
    {
        in >> arb[i];
    }
    for( int i= N2+N; i<=N2*2-1; ++i )
    {
        arb[i]= -INF;
    }
    for( int i= N2-1; i>=1; --i )
    {
        arb[i]= max( arb[i*2], arb[i*2+1] );
    }

    for( int q= 1; q<=M; ++q )
    {
        int a, b, c;
        in >> a >> b >> c;
        if( a==0 )
        {
            out << query( 1, b, c, 1, N2 ) << '\n';
        }
        else
        {
            int x= query( 1, b, b, 1, N2 );
            upd( 1, b, b, 1, N2, c-x );
        }

    }

    return 0;
}