1. #include <bits/stdc++.h>
  2. #define ll long long
  3. #define int long long
  4. #define fi first
  5. #define se second
  6. using namespace std;
  7. void db() {cout << '\n';}
  8. template <typename T, typename ...U> void db(T a, U ...b) {cout << a << ' ', db(b...);}
  9. #ifdef Cloud
  10. #define file freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout)
  11. #else
  12. #define file ios::sync_with_stdio(false); cin.tie(0)
  13. #endif
  14. const int N = 1e5 + 1, inf = 1e9;
  15. struct seg{
  16.     int l, r, mid, mi = inf, ma = 0;
  17.     seg *ch[2]{};
  18.     void set_mi(int pos, int val){
  19.         if (l == r) return void(mi = val);
  20.         if (pos <= mid) ch[0]->set_mi(pos, val);
  21.         else ch[1]->set_mi(pos, val);
  22.         mi = min(ch[0]->mi, ch[1]->mi);
  23.     }
  24.     void set_ma(int pos, int val){
  25.         if (l == r) return void(ma = val);
  26.         if (pos <= mid) ch[0]->set_ma(pos, val);
  27.         else ch[1]->set_ma(pos, val);
  28.         ma = max(ch[0]->ma, ch[1]->ma);
  29.     }
  30.     int qmi(int _l, int _r){
  31.         if (_l <= l and _r >= r) return mi;
  32.         if (_l > r or _r < l) return inf;
  33.         return min(ch[0]->qmi(_l, _r), ch[1]->qmi(_l, _r));
  34.     }
  35.     int qma(int _l, int _r){
  36.         if (_l <= l and _r >= r) return ma;
  37.         if (_l > r or _r < l) return 0;
  38.         return max(ch[0]->qma(_l, _r), ch[1]->qma(_l, _r));
  39.     }
  40.     seg (int _l, int _r): l(_l), r(_r), mid(l + r >> 1){
  41.         if (l < r) ch[0] = new seg(l, mid), ch[1] = new seg(mid + 1, r);
  42.     }
  43. };
  44. signed main(){
  45.     file;
  46.     int n, q;
  47.     cin >> n >> q;
  48.     int a[n];
  49.     for (int &i : a) cin >> i;
  50.     seg *rt = new seg(0, n - 1);
  51.     auto f = [&](int i){
  52.         rt->set_mi(i, inf);
  53.         rt->set_ma(i, 0);
  54.         if (a[i] == a[i + 1]) return;
  55.         if (a[i] < a[i + 1]) rt->set_mi(i, a[i] + a[i + 1] >> 1);
  56.         if (a[i] > a[i + 1]) rt->set_ma(i, (a[i] + a[i + 1] + 1) >> 1); 
  57.     };
  58.     for (int i = 0; i < n - 1; i++) f(i);
  59.     while (q--){
  60.         int tp, x, y;
  61.         cin >> tp >> x >> y;
  62.         if (tp == 1){
  63.             x--;
  64.             a[x] = y;
  65.             if (x < n - 1) f(x);
  66.             if (x) f(x - 1);
  67.         }
  68.         else{
  69.             x--, y--;
  70.             int l = rt->qma(x, y - 1), r = rt->qmi(x, y - 1);
  71.             if (l > r) cout << -1 << '\n';
  72.             else cout << l << '\n';
  73.         }
  74.     }
  75. }