#include <bits/stdc++.h>

using namespace std;


struct treap{
  int pos, val, max, pri;
  treap* left, *right;
  treap()
  {
    pos = 0;
    val = 0;
    max = 0;
    left = right = NULL;
    pri = rand();
  }
  treap(int _pos, int _val)
  {
    pos = _pos;
    val = _val;
    max = _val;
    pri = rand();
    left = right = NULL;
  }

}*root;


void show(treap *r)
{
  if(!r) return;
  cout << r->pri << ':' << r->val << "   sum: " << r->max << ' ' << " --- ";

  if(r->left) cout << "l: " << r->left->val << ':' << r->left->pri << ' ';
  if(r->right) cout << "r: " << r->right->val << ':' << r->right->pri << ' ';
  cout << '\n';

  show(r->left);
  show(r->right);
}


void update(treap* node)
{
  if(node == NULL) return;
  node->max = node->val;
  if(node->left) node->max = max(node->left->max, node->max);
  if(node->right) node->max = max(node->right->max, node->max);
}

void split(treap* root, int key, treap* &left, treap* &right)
{
  if(root == NULL)
    left = right = NULL;
  else if(key < root->pos)
    split(root->left, key, left, root->left),
    right = root;
  else
    split(root->right, key, root->right, right),
    left = root;

  update(left);
  update(right);
  //update(root);
}


void merge(treap* &root, treap* left, treap* right)
{
  if(left == NULL || right == NULL) root = left ? left : right;
  else if(left->pri > right ->pri)
    merge(left->right, left->right, right),
    root = left;
  else
    merge(right->left, left, right->left),
    root = right;

  update(left);
  update(right);
  //update(root);
}


int query(treap* root, int l, int r)
{
  int Max = 0;
  treap *mid, *left, *right;

  split(root, l-1, left, mid);
  split(mid, r, mid, right);
  update(mid);
  if(mid != NULL)
    Max = mid -> max;

  merge(mid, mid, right);
  merge(root, left, mid);
  return Max;
}

void add(treap* &root, int pos, int val)
{
  treap *l, *r, *mid;

  split(root, pos, l, r);
  split(l, pos-1, l, mid);

  if(mid) delete mid;
  mid = new treap(pos, val); //, cout << "ff " ;

  merge(l, l, mid);
  merge(root, l, r);

}


int main()
{

  ios_base :: sync_with_stdio(false);
  freopen("arbint.in", "r", stdin);
  freopen("arbint.out", "w", stdout);

  int a, b, c, n, m;
  srand(4598);

  cin >> n >> m;

  for(int i=1; i<=n; i++)
  {
    cin>>a;
    add(root, i, a);
  }

  for(int i=1; i<=m; i++)
  {
    cin >> a >> b >> c;
    if(a == 0)
      cout << query(root, b, c) <<'\n';
    else 
      add(root, b, c);
  }


}