#include <bits/stdc++.h>

using namespace std;

struct Splay {
  struct Node {
    int p = -1, ch[2] = {-1, -1};
    int dp, val;
  };
  vector<Node> T;
  
  Splay(int n) : T(n) {}

  void push(int x) {}
  void pull(int x) {
    T[x].dp = T[x].val;
    for (int y : {T[x].ch[0], T[x].ch[1]}) 
      if (~y) T[x].dp = max(T[x].dp, T[y].dp);
  }

  void set(int x, int d, int y) {
    T[x].ch[d] = y, pull(x);
    if (~y) T[y].p = x;
  }
  int dir(int x) {
    for (int p = T[x].p, z = 0; z < 2; ++z) 
      if ((~p) && T[p].ch[z] == x)
        return z;
    return -1;
  }
  void rotate(int x) {
    int y = T[x].p, z = T[y].p, dx = dir(x), dy = dir(y);
    set(y, dx, T[x].ch[!dx]); set(x, !dx, y);
    if (~dy) set(z, dy, x); else T[x].p = z;
  }
  void splay(int x) {
    while (~dir(x)) {
      int y = T[x].p, z = T[y].p, dx = dir(x), dy = dir(y);
      push(z), push(y), push(x);
      if (~dy) rotate(dx != dy ? x : y);
      rotate(x);
    }
  }

  void Update(int pos, int val) {
    splay(pos); T[pos].val = val; pull(pos);
  }
  void split(int x) {
    splay(x); 
    set(x, 0, -1);
  }
  void join(int x) {
    if (!x) return;
    splay(x); splay(x - 1); 
    set(x, 0, x - 1);
  }
  int Query(int b, int e) {
    split(e); split(b);
    int ret = T[b].dp;
    join(b); join(e);
    return ret;
  }
};

int main() {
  ifstream cin("arbint.in");
  ofstream cout("arbint.out");
  int n, m; cin >> n >> m;
  Splay S(n + 1);
  for (int i = 0; i < n; ++i) 
    cin >> S.T[i].val;
  S.T[n].val = 0;
  for (int i = 1; i <= n; ++i)
    S.set(i, 0, i - 1);
  
  for (int i = 0; i < m; ++i) {
    int t, a, b; cin >> t >> a >> b; --a;
    if (t == 0) cout << S.Query(a, b) << '\n';
    else S.Update(a, b);
  }

  return 0;
}