#include <bits/stdc++.h>
#define ll long long
#define MAXA 500002
#define MAXN 500000
using namespace std;
// (count and sum)
pair<ll,ll> tree[MAXA+2];
int A[MAXN+2];
void update(int idx, int val, int delta) {
    while(idx <= MAXA) {
        tree[idx].first += delta; // count
        tree[idx].second += delta*val; // sum
        idx += idx & -idx;
    }
}
pair<ll,ll> read(int idx) {
    pair<ll,ll> sum = {0,0};
    while(idx > 0) {
        sum.first += tree[idx].first;
        sum.second += tree[idx].second;
        idx -= idx & -idx;
    }
    return sum;
}
int main() {
    int N,Q;
    cin>>N>>Q;
    for(int i=0;i<=MAXA;i++) {
        tree[i] = {0,0};
    }
    for(int i=1;i<=N;i++){
        int a;
        cin>>a;
        A[i]=a;
        update(a+1, a, 1);
    }
    for(int q=1;q<=Q;q++) {
        int type;
        cin>>type;
        if (type==1) {
            int x,y;
            cin>>x>>y;
            update(A[x]+1, A[x], -1);
            A[x]=y;
            update(A[x]+1, A[x], 1);
        } else {
            ll l,r;
            cin>>l>>r;
            if (l >= r) {
                cout << l*N << endl;
                continue;
            }
            ll ans = read(r+1).second - read(l).second;
            ans += l*read(l).first;
            ans += (N - read(r+1).first)*r;
            cout<<ans<<"\n";
        }
    }
}