#include <bits/stdc++.h>

using namespace std;

#define cin fin
#define cout fout
ifstream cin("arbint.in");
ofstream cout("arbint.out");

const int nmax = 1e5 + 5;

template<typename Node, typename Lazy, int NMAX> struct AINT {
  Node aint[NMAX * 4];
  Lazy lazy[NMAX * 4];
  Node Nid;
  Lazy Lid;
  int *N;
  AINT(Node A, Lazy B, int nprim): Nid(A), Lid(B), N(&nprim) {;}
  void constr(int l, int r, Node *v, bool ok = 1, int node = 1, int cl = 1, int cr = NMAX) {
    int mid = cl + cr >> 1;
    switch (ok) {
      case 0: {
        if(cl == cr) {
          aint[node] = v[cl];
          return;
        }
        if(cr < l || r < cl)
          return;
        break;
      }
      
      case 1: {
        if(l <= cl && cr <= r) {
          constr(l, r, v, 0, node, cl, cr);
          return;
        }
        if(cr < l || r < cl)
          return;
        break;
      }
    }
    constr(l, r, v, ok, 2 * node, cl, mid);
    constr(l, r, v, ok, 2 * node + 1, mid + 1, cr);
    aint[node] = aint[2 * node] + aint[2 * node + 1];
  }
  void updp(int poz, Node val, int node = 1, int cl = 1, int cr = NMAX) {
    if(cl == cr) {
      aint[node] = val;
      return;
    }
    int mid = cl + cr >> 1;
    if(poz <= mid)
      updp(poz, val, 2 * node, cl, mid);
    else
      updp(poz, val, 2 * node + 1, mid + 1, cr);
    aint[node] = aint[2 * node] + aint[2 * node + 1];
  }
  void apply(int node, bool prop) {
    aint[node] += lazy[node];
    if(prop)
      lazy[2 * node] += lazy[node],
      lazy[2 * node + 1] += lazy[node];
    lazy[node] = Lid;
  }
  void updr(int l, int r, Lazy val, int node = 1, int cl = 1, int cr = NMAX) {
    apply(node, cl != cr);
    if(cr < l || r < cl)
      return;
    if(l <= cl && cr <= r) {
      lazy[node] += val;
      apply(node, cl != cr);
      return;
    }
    int mid = cl + cr >> 1;
    updr(l, r, val, 2 * node, cl, mid);
    updr(l, r, val, 2 * node + 1, mid + 1, cr);
    aint[node] = aint[2 * node] + aint[2 * node + 1];
  }
  Node query(int l, int r, int node = 1, int cl = 1, int cr = NMAX) {
    if(cr < l || r < cl)
      return Nid;
    if(l <= cl && cr <= r) {
      return aint[node];
    }
    int mid = cl + cr >> 1;
    return query(l, r, 2 * node, cl, mid) + query(l, r, 2 * node + 1, mid + 1, cr);
  }
};

struct _int {
  int x;
  _int operator +(const _int& y) const {
    return _int{max(x, y.x)};
  }
  _int operator +(const int& y) const {
    return (*this);
  }
};
_int v[nmax];

int main() {
   int n, m;
  cin >> n >> m;
  for(int i = 1, x; i <= n; i++) {
    cin >> x;
    v[i].x = x;
  }
  AINT<_int, int, nmax> aint(_int{0}, 0, n);
  aint.constr(1, n, v);
  for(int i = 0, t, a, b; i < m; i++) {
    cin >> t >> a >> b;
    if(t == 0)
      cout << aint.query(a, b).x << '\n';
    else
      aint.updp(a, _int{b});
  }
}