#include <stdio.h>
#include <stdlib.h>

#define NMAX 100000

int n, op;
int aint[1 + 4 * NMAX];
int a, b, ans;

int abs ( int x ) {
    return ( x < 0 ) ? -x : x;
}

int maxim ( int a, int b ) {
    return ( a + b + abs ( a - b ) ) >> 1;
}

void update ( int p, int st, int dr ) {
    int mid = ( st + dr ) / 2;

    if ( st == dr )
        aint[p] = b;
    else {
        if ( a <= mid )
            update ( 2 * p, st, mid );
        else
            update ( 2 * p + 1, mid + 1, dr );
        aint[p] = maxim ( aint[2 * p], aint[2 * p + 1] );
    }
}

void query ( int p, int st, int dr ) {
    int mid = ( st + dr ) / 2;

    if ( a <= st && dr <= b )
        ans = maxim ( ans, aint[p] );
    else {
        if ( a <= mid )
            query ( 2 * p, st, mid );
        if ( b > mid )
            query ( 2 * p + 1, mid + 1, dr );
    }
}


int main() {
    FILE *fin = fopen ( "arbint.in", "r" );
    fscanf ( fin, "%d%d", &n, &op );
    int i, x;
    for ( i = 1; i <= n; ++i ) {
        fscanf ( fin, "%d", &x );
        a = i;
        b = x;
        update ( 1, 1, n );
    }

    FILE *fout = fopen ( "arbint.out", "w" );
    for ( i = 1; i <= op; ++i ) {
        int p;
        fscanf ( fin, "%d%d%d", &p, &a, &b );
        if ( p == 0 ) {
            ans = 0;
            query ( 1, 1, n );
            fprintf ( fout, "%d\n", ans );
        } else
            update ( 1, 1, n );
    }

    fclose ( fout );
    fclose ( fin );

    return 0;
}