#include <stdio.h>

#define MAX_N 100000
#define MAX_SQR 317

int v[MAX_N]; // vectorul de elemente
int s[MAX_SQR]; // bucket-uri de marime sqrt(n)
int n, bucketSize;

inline int min(const int &a, const int &b) {
  return a < b ? a : b;
}
inline int max(const int &a, const int &b) {
  return a > b ? a : b;
}

inline void update(const int &p, const int &x) {
  int bucket = p / bucketSize;

  if (s[bucket] == v[p]) {
    s[bucket] = 0;
    v[p] = x;
    int l = bucket * bucketSize + bucketSize;
    for (int i = bucket * bucketSize; i < l; i++) {
      if (v[i] > s[bucket]) {
        s[bucket] = v[i];
      }
    }
  } else {
    if (x > s[bucket]) {
      s[bucket] = x;
    }
    v[p] = x;
  }
}
inline int query(const int &a, const int &b) {
  int bucket[2] = {a / bucketSize, b / bucketSize};
  int ans = 0;

  for (int i = bucket[0] + 1; i < bucket[1]; i++) { // bucket-uri
    if(s[i] > ans) {
      ans = s[i];
    }
  }
  if (ans < s[bucket[0]]) { // resturi stanga
    int l = min(bucket[0] * bucketSize + bucketSize, b + 1);
    for (int i = a; i < l; i++) {
      if (v[i] > ans) {
        ans = v[i];
      }
    }
  }
  if (ans < s[bucket[1]]) { // resturi dreapta
    for (int i = max(a, bucket[1] * bucketSize); i <= b; i++) {
      if (v[i] > ans) {
        ans = v[i];
      }
    }
  }
  return ans;
}
int main(void) {
  FILE *f, *g;
  int testNum;
  int a, b;

  f = fopen("aint.in", "r");
  fscanf(f, "%d%d", &n, &testNum);

  bucketSize = 1;
  while (bucketSize * bucketSize <= n) {
    bucketSize++;
  }
  bucketSize--;

  for (int i = 0; i < n; i++) {
    fscanf(f, "%d ", &v[i]);
    int bucket = (i / bucketSize);
    if (v[i] > s[bucket])
      s[bucket] = v[i];
  }

  g = fopen("aint.out", "w");
  for (; testNum; testNum--) {
    char c = fgetc(f);
    fscanf(f, "%d%d ", &a, &b);
    switch (c) {
    case '0':
      fprintf(g, "%d\n", query(a - 1, b - 1));
      break;
    case '1':
      update(a - 1, b);
      break;
    }
  }
  fclose(f);
  fclose(g);
  return 0;
}