#include<bits/stdc++.h>
#define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL)
using namespace std;
#define int long long
class SegTree{
vector<int>seg;
public:
vector<int>index;
SegTree(int n){
seg.resize(4*n+1);
}
void build(int ind, int low, int high, vector<int>&buckets){
if(low==high){
seg[ind] = buckets[low];
return;
}
int mid = low+ ((high-low)>>1);
build(2*ind+1, low, mid, buckets);
build(2*ind+2, mid+1, high, buckets);
seg[ind] = seg[2*ind+1] + seg[2*ind+2];
}
int query(int ind, int low, int high, int l, int r){
if(high<l || low>r) return 0;
if(low>=l && high<=r) return seg[ind];
int mid = low+ ((high-low)>>1);
return query(2*ind+1,low,mid,l,r) + query(2*ind+2,mid+1,high,l,r);
}
void update(int ind, int low,int high, int key,int val){
if(low==high){
seg[ind] = val;
return;
}
int mid = (low+high)/2;
if(key<=mid) update(2*ind+1,low,mid,key,val);
else update(2*ind+2,mid+1,high,key,val);
seg[ind] = seg[2*ind+1] + seg[2*ind+2];
}
};
int buck_no(int x){
if(x%100==0) x--;
return x/100;
}
int calc(int lo,map<int,int>&mp,int hi){
int ans = 0;
for(int i=lo;i<=hi;i++){
ans+=mp[i];
}
return ans;
}
void solve(){
int n,q; cin>>n>>q;
vector<int>a(n);
map<int,int>mp;
vector<int>buckets(10000000);
for(int i=0;i<n;i++) {
cin>>a[i];
mp[a[i]]++;
buckets[buck_no(a[i])]++;
}
SegTree sg(10000000);
sg.build(0,0,10000000,buckets);
for(int i=0;i<q;i++){
char op; cin>>op;
int x,y; cin>>x>>y;
if(op=='?'){
int ans = calc(x,mp,min(y,(buck_no(x)+1)*100));
if(buck_no(x)!=buck_no(y)) {
ans+=calc(max(x,buck_no(y)*100+1),mp,y);
}
ans += sg.query(0,0,10000000,buck_no(x)+1,buck_no(y)-1);
cout<<ans<<endl;
}
else {
sg.update(0,0,10000000,buck_no(a[x-1]),--buckets[buck_no(a[x-1])]);
sg.update(0,0,10000000,buck_no(y),++buckets[buck_no(y)]);
mp[a[x-1]]--; mp[y]++;
a[x-1] = y;
}
}
}
signed main(){
solve();
cout<<endl;
}
I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KI2RlZmluZSBmYXN0X2lvIGlvc19iYXNlOjpzeW5jX3dpdGhfc3RkaW8oZmFsc2UpO2Npbi50aWUoTlVMTCkKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKI2RlZmluZSBpbnQgbG9uZyBsb25nCgpjbGFzcyBTZWdUcmVlewogICAgdmVjdG9yPGludD5zZWc7CiAgICBwdWJsaWM6CiAgICAgICAgdmVjdG9yPGludD5pbmRleDsKICAgICAgICBTZWdUcmVlKGludCBuKXsKICAgICAgICAgICAgc2VnLnJlc2l6ZSg0Km4rMSk7CiAgICAgICAgfQogICAgICAgIHZvaWQgYnVpbGQoaW50IGluZCwgaW50IGxvdywgaW50IGhpZ2gsIHZlY3RvcjxpbnQ+JmJ1Y2tldHMpewogICAgICAgICAgICBpZihsb3c9PWhpZ2gpewogICAgICAgICAgICAgICAgc2VnW2luZF0gPSBidWNrZXRzW2xvd107CiAgICAgICAgICAgICAgICByZXR1cm47CiAgICAgICAgICAgIH0KICAgICAgICAgICAgaW50IG1pZCA9IGxvdysgKChoaWdoLWxvdyk+PjEpOwogICAgICAgICAgICBidWlsZCgyKmluZCsxLCBsb3csIG1pZCwgYnVja2V0cyk7CiAgICAgICAgICAgIGJ1aWxkKDIqaW5kKzIsIG1pZCsxLCBoaWdoLCBidWNrZXRzKTsKICAgICAgICAgICAgc2VnW2luZF0gPSBzZWdbMippbmQrMV0gKyBzZWdbMippbmQrMl07CiAgICAgICAgfQogICAgICAgIAogICAgICAgIGludCBxdWVyeShpbnQgaW5kLCBpbnQgbG93LCBpbnQgaGlnaCwgaW50IGwsIGludCByKXsKICAgICAgICAgICAgaWYoaGlnaDxsIHx8IGxvdz5yKSByZXR1cm4gMDsKICAgICAgICAgICAgaWYobG93Pj1sICYmIGhpZ2g8PXIpIHJldHVybiBzZWdbaW5kXTsKICAgICAgICAgICAgaW50IG1pZCA9IGxvdysgKChoaWdoLWxvdyk+PjEpOwogICAgICAgICAgICByZXR1cm4gcXVlcnkoMippbmQrMSxsb3csbWlkLGwscikgKyBxdWVyeSgyKmluZCsyLG1pZCsxLGhpZ2gsbCxyKTsKICAgICAgICB9CiAgICAgICAgCiAgICAgICAgdm9pZCB1cGRhdGUoaW50IGluZCwgaW50IGxvdyxpbnQgaGlnaCwgaW50IGtleSxpbnQgdmFsKXsKICAgICAgICAgICAgaWYobG93PT1oaWdoKXsKICAgICAgICAgICAgICAgIHNlZ1tpbmRdID0gdmFsOwogICAgICAgICAgICAgICAgcmV0dXJuOwogICAgICAgICAgICB9CiAgICAgICAgICAgIGludCBtaWQgPSAobG93K2hpZ2gpLzI7CiAgICAgICAgICAgIGlmKGtleTw9bWlkKSB1cGRhdGUoMippbmQrMSxsb3csbWlkLGtleSx2YWwpOwogICAgICAgICAgICBlbHNlIHVwZGF0ZSgyKmluZCsyLG1pZCsxLGhpZ2gsa2V5LHZhbCk7CiAgICAgICAgICAgIHNlZ1tpbmRdID0gc2VnWzIqaW5kKzFdICsgc2VnWzIqaW5kKzJdOwogICAgICAgIH0KICAgICAgICAKfTsKCmludCBidWNrX25vKGludCB4KXsKICAgIGlmKHglMTAwPT0wKSB4LS07CiAgICByZXR1cm4geC8xMDA7Cn0KCmludCBjYWxjKGludCBsbyxtYXA8aW50LGludD4mbXAsaW50IGhpKXsKICAgIGludCBhbnMgPSAwOwogICAgZm9yKGludCBpPWxvO2k8PWhpO2krKyl7CiAgICAgICAgYW5zKz1tcFtpXTsKICAgIH0KICAgIHJldHVybiBhbnM7Cn0KCnZvaWQgc29sdmUoKXsKICAgIGludCBuLHE7IGNpbj4+bj4+cTsKICAgIHZlY3RvcjxpbnQ+YShuKTsKICAgIG1hcDxpbnQsaW50Pm1wOwogICAgdmVjdG9yPGludD5idWNrZXRzKDEwMDAwMDAwKTsKICAgIGZvcihpbnQgaT0wO2k8bjtpKyspIHsKICAgICAgICBjaW4+PmFbaV07CiAgICAgICAgbXBbYVtpXV0rKzsKICAgICAgICBidWNrZXRzW2J1Y2tfbm8oYVtpXSldKys7CiAgICB9CiAgICBTZWdUcmVlIHNnKDEwMDAwMDAwKTsKICAgIHNnLmJ1aWxkKDAsMCwxMDAwMDAwMCxidWNrZXRzKTsKICAgIAogICAgZm9yKGludCBpPTA7aTxxO2krKyl7CiAgICAgICAgY2hhciBvcDsgY2luPj5vcDsKICAgICAgICBpbnQgeCx5OyBjaW4+Png+Pnk7CiAgICAgICAgaWYob3A9PSc/Jyl7CiAgICAgICAgICAgIGludCBhbnMgPSBjYWxjKHgsbXAsbWluKHksKGJ1Y2tfbm8oeCkrMSkqMTAwKSk7CiAgICAgICAgICAgIGlmKGJ1Y2tfbm8oeCkhPWJ1Y2tfbm8oeSkpIHsKICAgICAgICAgICAgICAgIGFucys9Y2FsYyhtYXgoeCxidWNrX25vKHkpKjEwMCsxKSxtcCx5KTsKICAgICAgICAgICAgfQogICAgICAgICAgICBhbnMgKz0gc2cucXVlcnkoMCwwLDEwMDAwMDAwLGJ1Y2tfbm8oeCkrMSxidWNrX25vKHkpLTEpOwogICAgICAgICAgICBjb3V0PDxhbnM8PGVuZGw7CiAgICAgICAgfQogICAgICAgIGVsc2UgewogICAgICAgICAgICBzZy51cGRhdGUoMCwwLDEwMDAwMDAwLGJ1Y2tfbm8oYVt4LTFdKSwtLWJ1Y2tldHNbYnVja19ubyhhW3gtMV0pXSk7CiAgICAgICAgICAgIHNnLnVwZGF0ZSgwLDAsMTAwMDAwMDAsYnVja19ubyh5KSwrK2J1Y2tldHNbYnVja19ubyh5KV0pOwogICAgICAgICAgICBtcFthW3gtMV1dLS07IG1wW3ldKys7CiAgICAgICAgICAgIGFbeC0xXSA9IHk7CiAgICAgICAgfQogICAgfQp9CnNpZ25lZCBtYWluKCl7CiAgICBzb2x2ZSgpOwogICAgY291dDw8ZW5kbDsKfQ==