#include<bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL)
#define ll long long
#define ld long double
#define pb push_back
#define fe first
#define se second
#define nl "\n"
#define pp pair < ll , ll >
#define sz(x) (ll)x.size()
#define st(x) sort(x.begin(),x.end())
#define rst(x) sort(x.rbegin(), x.rend())
#define all(x) x.begin(),x.end()
long double pi = 3.14159265358979323;
const double EPS = 1e-12;
const int N = 6*1e5 + 10;
const int mod = 1e9 + 7;
int BIT[ 4 * N ] ;
void update( int pos, int val ){
while( pos < N ){
BIT[ pos ] += val ;
pos += ( pos & -pos ) ;
}
}
int query( int pos ){
int ans( 0 ) ;
while( pos ){
ans += BIT[ pos ] ;
pos -= ( pos & -pos ) ;
}
return ans ;
}
struct query{
char t ;
int l, r ;
}qrr[ N ] ;
int ar[ N ] ;
set< int > st ;
map< int, int > mpp ;
int main()
{
fast;
int n, q ;
cin >> n >> q ;
for( int i = 1 ; i <= n ; i++ ){
cin >> ar[ i ] ;
st.insert( ar[ i ] ) ;
}
for( int i = 0 ; i < q ; i++ ){
cin >> qrr[ i ].t >> qrr[ i ].l >> qrr[ i ].r ;
st.insert( qrr[ i ].r ) ;
st.insert( qrr[ i ].l ) ;
}
int ind( 1 ) ;
for( int i : st )
mpp[ i ] = ind++ ;
for( int i = 1 ; i <= n ; i++ ){
int pos = mpp[ ar[ i ] ] ;
ar[ i ] = pos ;
update( pos, 1 ) ;
}
for( int i = 0 ; i < q ; i++ ){
char t = qrr[ i ].t ;
int l = qrr[ i ].l ;
int r = qrr[ i ].r ;
if( t == '?' ){
l = mpp[ l ] ;
r = mpp[ r ] ;
cout << query( r ) - query( l - 1 ) << '\n' ;
}
else{
int prev = ar[ l ] ;
update( prev, -1 ) ;
r = mpp[ r ] ;
update( r, 1 ) ;
ar[ l ] = r ;
}
}
}
I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKIAojZGVmaW5lIGZhc3QgaW9zX2Jhc2U6OnN5bmNfd2l0aF9zdGRpbygwKTtjaW4udGllKE5VTEwpO2NvdXQudGllKE5VTEwpCiNkZWZpbmUgbGwgbG9uZyBsb25nCiNkZWZpbmUgbGQgbG9uZyBkb3VibGUKI2RlZmluZSBwYiBwdXNoX2JhY2sKI2RlZmluZSBmZSBmaXJzdAojZGVmaW5lIHNlIHNlY29uZAojZGVmaW5lIG5sICJcbiIKI2RlZmluZSBwcCBwYWlyIDwgbGwgLCBsbCA+IAojZGVmaW5lIHN6KHgpIChsbCl4LnNpemUoKQojZGVmaW5lIHN0KHgpIHNvcnQoeC5iZWdpbigpLHguZW5kKCkpCiNkZWZpbmUgcnN0KHgpIHNvcnQoeC5yYmVnaW4oKSwgeC5yZW5kKCkpCiNkZWZpbmUgYWxsKHgpIHguYmVnaW4oKSx4LmVuZCgpCmxvbmcgZG91YmxlIHBpID0gMy4xNDE1OTI2NTM1ODk3OTMyMzsKIApjb25zdCBkb3VibGUgRVBTID0gMWUtMTI7CmNvbnN0IGludCBOID0gNioxZTUgKyAxMDsKY29uc3QgaW50IG1vZCA9IDFlOSArIDc7CiAKaW50IEJJVFsgNCAqIE4gXSA7IAogCnZvaWQgdXBkYXRlKCBpbnQgcG9zLCBpbnQgdmFsICl7CiAgd2hpbGUoIHBvcyA8IE4gKXsKICAgIEJJVFsgcG9zIF0gKz0gdmFsIDsKICAgIHBvcyArPSAoIHBvcyAmIC1wb3MgKSA7CiAgfQp9CiAKaW50IHF1ZXJ5KCBpbnQgcG9zICl7CiAgaW50IGFucyggMCApIDsKICB3aGlsZSggcG9zICl7CiAgICBhbnMgKz0gQklUWyBwb3MgXSA7CiAgICBwb3MgLT0gKCBwb3MgJiAtcG9zICkgOwogIH0KICByZXR1cm4gYW5zIDsKfQogCnN0cnVjdCBxdWVyeXsKICAgY2hhciB0IDsKICAgaW50IGwsIHIgOwp9cXJyWyBOIF0gOwogCmludCBhclsgTiBdIDsKc2V0PCBpbnQgPiBzdCA7Cm1hcDwgaW50LCBpbnQgPiBtcHAgOwogCmludCBtYWluKCkKewogICAgZmFzdDsKIAogICAgaW50IG4sIHEgOwogICAgY2luID4+IG4gPj4gcSA7CiAKICAgIGZvciggaW50IGkgPSAxIDsgaSA8PSBuIDsgaSsrICl7CiAgICAgIGNpbiA+PiBhclsgaSBdIDsKICAgICAgc3QuaW5zZXJ0KCBhclsgaSBdICkgOwogICAgfQogCiAgICBmb3IoIGludCBpID0gMCA7IGkgPCBxIDsgaSsrICl7CiAgICAgIGNpbiA+PiBxcnJbIGkgXS50ID4+IHFyclsgaSBdLmwgPj4gcXJyWyBpIF0uciA7CiAgICAgICAgIHN0Lmluc2VydCggcXJyWyBpIF0uciApIDsKICAgICAgICAgc3QuaW5zZXJ0KCBxcnJbIGkgXS5sICkgOwogICAgfQogCiAgIGludCBpbmQoIDEgKSA7CiAgIGZvciggaW50IGkgOiBzdCApCiAgICAgIG1wcFsgaSBdID0gaW5kKysgOwogICBmb3IoIGludCBpID0gMSA7IGkgPD0gbiA7IGkrKyApewogICAgICBpbnQgcG9zID0gbXBwWyBhclsgaSBdIF0gOwogICAgICBhclsgaSBdID0gcG9zIDsKICAgICAgdXBkYXRlKCBwb3MsIDEgKSA7CiAgIH0KICAgCiAgIGZvciggaW50IGkgPSAwIDsgaSA8IHEgOyBpKysgKXsKICAgICAgY2hhciB0ID0gcXJyWyBpIF0udCA7CiAgICAgIGludCBsID0gcXJyWyBpIF0ubCA7CiAgICAgIGludCByID0gcXJyWyBpIF0uciA7CiAgICAgIGlmKCB0ID09ICc/JyApewogICAgICAgICBsID0gbXBwWyBsIF0gOwogICAgICAgICByID0gbXBwWyByIF0gOwogICAgICAgICBjb3V0IDw8IHF1ZXJ5KCByICkgLSBxdWVyeSggbCAtIDEgKSA8PCAnXG4nIDsKICAgICAgfQogICAgICBlbHNlewogICAgICAgICBpbnQgcHJldiA9IGFyWyBsIF0gOwogICAgICAgICB1cGRhdGUoIHByZXYsIC0xICkgOwogICAgICAgICByID0gbXBwWyByIF0gOwogICAgICAgICB1cGRhdGUoIHIsIDEgKSA7CiAgICAgICAgIGFyWyBsIF0gPSByIDsKICAgICAgfQogICB9Cn0=