#include <bits/stdc++.h>
#define for0(i,n) for(int i=0; i<n; i++)
#define for1(i,n) for(int i=1; i<=n; i++)
#define pb push_back
#define mp make_pair
#define all(v) v.begin(), v.end()
#define V vector<int>
#define VP vector<pair<int, int> >
#define clr(A,x) memset(A, x, sizeof(A))
#define cpy(A,B) memcpy(A, B, sizeof(B))
#define g(s) getline(cin, s) ///ai grija la fin/cin ///
#define FASTIO ios_base::sync_with_stdio(0)
#define INF 0x3f3f3f3f
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

const int CHARMAX = (1 << 10);
const int INFINT = 2000000000;
const ll INFLL = (1LL << 62);

class InParsare
{
private:
    FILE *fin;
    char *buffer;
    size_t index_of_buffer;

    char read_character()
    {
        index_of_buffer++;
        if(index_of_buffer == CHARMAX)
        {
            fread(buffer, 1, CHARMAX, fin);
            index_of_buffer = 0;
        }
        return buffer[index_of_buffer];
    }

public:
    InParsare(const char *name)
    {
        fin = fopen(name, "r");
        buffer = new char[CHARMAX]();
        index_of_buffer = CHARMAX - 1;
    }

    template<class T>
    InParsare &operator >> (T &n)
    {
        char c;
        while(!isdigit(c = read_character()) && c != '-');

        int sgn = 1;
        if(c == '-')
        {
            n = 0;
            sgn = -1;
        }
        else n = c - '0';

        while(isdigit(c = read_character()))
            n = n * 10 + c - '0';
        n *= sgn;

        return *this;
    }
};

class OutParsare
{
private:
    FILE *fout;
    char *buffer;
    size_t index_of_buffer;

    void write_character(char character)
    {
        if(index_of_buffer == CHARMAX)
        {
            fwrite(buffer, 1, CHARMAX, fout);
            index_of_buffer = 0;
            buffer[index_of_buffer++] = character;
        }
        else buffer[index_of_buffer++] = character;
    }

public:

    OutParsare(const char *name)
    {
        fout = fopen(name, "w");
        buffer = new char[CHARMAX]();
        index_of_buffer = 0;
    }

    ~OutParsare()
    {
        fwrite(buffer, 1, index_of_buffer, fout);
        fclose(fout);
    }
    template<class T>
    OutParsare &operator << (T n)
    {
        if(typeid(T).name() == typeid(char).name())
        {
            write_character(n);
            return *this;
        }

        if(n <= 9)
            write_character(n + '0');
        else
        {
            (*this) << (n / 10);
            write_character(n % 10 + '0');
        }

        return *this;
    }

};

//InParsare fin("nume.in"); /// merg numai pt numere
//OutParsare fout("nume.out"); /// merg numai pt numere + caractere individuale, nu stringuri
ifstream fin("arbint.in");
ofstream fout("arbint.out");

struct node
{
    int val, mmax, ssize, priority;
    node *left, *right;
} nil {-1, -1, 0, -1, 0x00, 0x00};

void calculations(node *nod)
{
    nod -> ssize = nod -> left -> ssize + nod -> right -> ssize + 1;
    nod -> mmax = max(nod -> val, max(nod -> left -> mmax, nod -> right -> mmax));
}

pair<node*, node*> split(node *nod, int pos)
{
    if(nod == &nil) return mp(&nil, &nil);

    if(nod -> left -> ssize == pos)
    {
        node *temp = nod -> left;
        nod -> left = &nil;
        calculations(nod);
        return mp(temp, nod);
    }

    if(nod -> left -> ssize < pos)
    {
        auto temp = split(nod -> right, pos - nod -> left -> ssize - 1);
        nod -> right = temp.first;
        calculations(nod);
        return mp(nod, temp.second);
    }

    if(nod -> left -> ssize > pos)
    {
        auto temp = split(nod -> left, pos);
        nod -> left = temp.second;
        calculations(nod);
        return mp(temp.first, nod);
    }

    return mp(&nil, &nil);
}

node* join(node *a, node *b)
{
    if(a == &nil) return b;
    if(b == &nil) return a;

    if(a -> priority > b -> priority)
    {
        a -> right = join(a -> right, b);
        calculations(a);
        return a;
    }
    else
    {
        b -> left = join(a, b -> left);
        calculations(b);
        return b;
    }

}

node* inseration(node *nod, int pos, int val)
{
    auto temp = split(nod, pos);
    temp.first = join(temp.first, new node {val, val, 1, rand(), &nil, &nil});
    return join(temp.first, temp.second);
}

void dfs(node *nod)
{
    if(nod -> left != &nil)
        dfs(nod -> left);
    cout << nod -> val << ' ';
    if(nod -> right != &nil)
        dfs(nod -> right);
}

node* update(node *nod, int pos, int val)
{
    pair<node*, node*> temp;
    if(pos == 0)
    {
        temp = split(nod, 1);
        return join(new node {val, val, 1, rand(), &nil, &nil}, temp.second);
    }

    temp = split(nod, pos);
    auto temp2 = split(temp.second, 1);
    temp2.second = join(new node {val, val, 1, rand(), &nil, &nil}, temp2.second);
    return join(temp.first, temp2.second);

}

node* query(node *nod, int x, int y)
{
    if(x == 0)
    {
        auto temp = split(nod, y + 1);
       // dfs(temp.first); cout << endl; dfs(temp.second); cout << endl;
        fout << temp.first -> mmax << '\n';
        return join(temp.first, temp.second);
    }

    if(y == nod -> ssize - 1)
    {
        auto temp = split(nod, x);
      //  dfs(temp.first); cout << endl; dfs(temp.second); cout << endl;
        fout << temp.second -> mmax << '\n';
        return join(temp.first, temp.second);
    }

    auto temp = split(nod, y + 1);
    auto temp2 = split(temp.first, x);
   // dfs(temp2.first); cout << '\n'; dfs(temp2.second); cout << '\n'; dfs(temp.second); cout << '\n'; //
    fout << temp2.second -> mmax << '\n';
    return join(temp2.first, join(temp2.second, temp.second));
}

// 10 5 0 1 2 3 4 5 6 7 8 9


int n, q, p;
node *root;

int main()
{
    root = &nil;
    fin >> n >> q;
    for0(i, n)
    {
        int value;
        fin >> value;
        root = inseration(root, i, value);
    }
  //  cout << root -> mmax << '\n';
  //  dfs(root);
    //cout << endl;
    for0(i, q)
    {
        fin >> p;
        if(p == 1)
        {
            int position, value;
            fin >> position >> value;
            root = update(root, position - 1, value);
        }
        else
        {
            int x, y;
            fin >> x >> y;
            if(x == 1 && y == n)
                fout << root -> mmax << '\n';
            else root = query(root, x - 1, y - 1);
        }

    }

    return 0;
}