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. }