#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';
        }
    }
}