- #include <bits/stdc++.h>
- #define ll long long
- #define int long long
- #define fi first
- #define se second
- using namespace std;
- void db() {cout << '\n';}
- template <typename T, typename ...U> void db(T a, U ...b) {cout << a << ' ', db(b...);}
- #ifdef Cloud
- #define file freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout)
- #else
- #define file ios::sync_with_stdio(false); cin.tie(0)
- #endif
- const int N = 1e5 + 1, inf = 1e9;
- struct seg{
- int l, r, mid, mi = inf, ma = 0;
- seg *ch[2]{};
- void set_mi(int pos, int val){
- if (l == r) return void(mi = val);
- if (pos <= mid) ch[0]->set_mi(pos, val);
- else ch[1]->set_mi(pos, val);
- mi = min(ch[0]->mi, ch[1]->mi);
- }
- void set_ma(int pos, int val){
- if (l == r) return void(ma = val);
- if (pos <= mid) ch[0]->set_ma(pos, val);
- else ch[1]->set_ma(pos, val);
- ma = max(ch[0]->ma, ch[1]->ma);
- }
- int qmi(int _l, int _r){
- if (_l <= l and _r >= r) return mi;
- if (_l > r or _r < l) return inf;
- return min(ch[0]->qmi(_l, _r), ch[1]->qmi(_l, _r));
- }
- int qma(int _l, int _r){
- if (_l <= l and _r >= r) return ma;
- if (_l > r or _r < l) return 0;
- return max(ch[0]->qma(_l, _r), ch[1]->qma(_l, _r));
- }
- seg (int _l, int _r): l(_l), r(_r), mid(l + r >> 1){
- if (l < r) ch[0] = new seg(l, mid), ch[1] = new seg(mid + 1, r);
- }
- };
- signed main(){
- file;
- int n, q;
- cin >> n >> q;
- int a[n];
- for (int &i : a) cin >> i;
- seg *rt = new seg(0, n - 1);
- auto f = [&](int i){
- rt->set_mi(i, inf);
- rt->set_ma(i, 0);
- if (a[i] == a[i + 1]) return;
- if (a[i] < a[i + 1]) rt->set_mi(i, a[i] + a[i + 1] >> 1);
- if (a[i] > a[i + 1]) rt->set_ma(i, (a[i] + a[i + 1] + 1) >> 1);
- };
- for (int i = 0; i < n - 1; i++) f(i);
- while (q--){
- int tp, x, y;
- cin >> tp >> x >> y;
- if (tp == 1){
- x--;
- a[x] = y;
- if (x < n - 1) f(x);
- if (x) f(x - 1);
- }
- else{
- x--, y--;
- int l = rt->qma(x, y - 1), r = rt->qmi(x, y - 1);
- if (l > r) cout << -1 << '\n';
- else cout << l << '\n';
- }
- }
- }