using namespace std;
#include                    <bits/stdc++.h>
#define     DB(x)           cerr << #x << " is " << (x) << endl;
#define     FIO             ios::sync_with_stdio(false);// cin.tie(nullptr); cout.tie(nullptr) // ===  === === === === === ===>
#define     pb              push_back
#define     fs              first
#define     sc              second
#define     endl            "\n"
typedef     long long           ll;
typedef     long double         ld;
int const mxn = 1e5+2;
int const mod = 1e9+7;

struct NOde{
    int s, mx, mn;
};

int n, q, aa[mxn];
NOde tt[mxn<<2];

NOde Join(NOde a, NOde b){
    NOde rs;
    rs.mn = min(a.mn,b.mn);
    rs.mx = max(a.mx,b.mx);
    rs.s = a.s + b.s;
    return rs;
}

void Build(int l, int r, int idx){
    if (l == r){
        tt[idx].s = tt[idx].mn = tt[idx].mx = aa[l];
        return;
    }
    int mid = (l+r)>>1;
    Build(l,mid,idx*2);
    Build(mid+1,r,idx*2+1);
    tt[idx] = Join(tt[idx*2],tt[idx*2+1]);
}

NOde Query(int l, int r, int u, int v, int idx){
    if (l > v || r < u) return {0,INT_MIN,INT_MAX};
    if (u <= l && r <= v) return tt[idx];
    int mid = (l+r)>>1;
    return Join(Query(l,mid,u,v,idx*2), Query(mid+1,r,u,v,idx*2+1));
}

void Update(int l, int r, int idx, int pos, int val){
    if (l == r){
        tt[idx].mn = tt[idx].mx = tt[idx].s = val;
        aa[l] = val;
        return;
    }
    int mid = (l+r)>>1;
    if (pos <= mid) Update(l,mid,idx*2,pos,val);
    else Update(mid+1,r,idx*2+1,pos,val);
    tt[idx] = Join(tt[idx*2],tt[idx*2+1]);
}

void SOL(){
    cin >> n >> q;
    for (int i=1; i<=n; ++i){
        cin >> aa[i];
    }
    Build(1,n,1);
    for (int i=1; i<=q; ++i){
        int x, l, r; cin >> x >> l >> r;
        if (x == 1){
            NOde node = Query(1,n,l,r,1);
            cout << node.s - node.mx - node.mn << "\n";
        } else {
            Update(1,n,1,l,r);
        }
    }
}
/*
*/
int main(){FIO; SOL(); return 0;}