#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pii pair<int, int>
#define f first
#define s second
#define mp make_pair
 
 
map<int, int> valtoID;
pair<int, pii> queries[(int)2e5+5];
int arr[(int)2e5+5];
 
ll fwt[(int)1e6];
ll sum(int i)
{
    ll sum = 0;
    while(i > 0){
        sum += fwt[i];
        i -= (i & -i);  //least important bit
    }
    return sum;
}
ll query(int a, int b)
{
    return sum(b) - sum(a - 1);
}
void update(int i, ll v)
{
    while(i > 0 && i < 1e6){
        fwt[i] += v;
        i += (i & -i);
    }
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
 
    int n, q;
    cin >> n >> q;
    for(int i = 0; i < n; i++){
        cin >> arr[i];
        valtoID[arr[i]] = 0;
    }
    for(int i = 0; i < q; i++){
        char t; int l, r, type; cin >> t >> l >> r;
        valtoID[r] = 0;
        if(t == '?'){
            type = 2;
        }
        else{
            type = 1;
            valtoID[l] = 0;
        }
        queries[i] = mp(type, mp(l, r));
    }
    int ID = 1;
    for(auto &t : valtoID){
        t.s = ID++;
    }

    for(int i = 0; i < n; i++){
        arr[i] = valtoID[arr[i]];
        update(arr[i], 1);
    }
    for(int i = 0; i < q; i++){
    	int type = queries[i].f;
        if(type == 1){
            update(arr[queries[i].s.f - 1], -1);
            int r = valtoID[queries[i].s.s];
            arr[queries[i].s.f - 1] = r;
            update(r, 1);
        }
        else{
            int l = valtoID[queries[i].s.f];
            int r = valtoID[queries[i].s.s];
            cout << query(l, r) << endl;
        }
    }
 
    return 0;
}