#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 ] ;
vector< int > v ;
map< int, int > mpp ;
int main()
{
fast;
int n, q ;
cin >> n >> q ;
for( int i = 1 ; i <= n ; i++ ){
cin >> ar[ i ] ;
v.pb( ar[i] );
}
for( int i = 0 ; i < q ; i++ ){
cin >> qrr[ i ].t >> qrr[ i ].l >> qrr[ i ].r ;
v.pb( qrr[ i ].r ) ;
v.pb( qrr[ i ].l ) ;
}
int ind( 2 ) ;
sort( all( v ) ) ;
mpp[ v[ 0 ] ] = 1 ;
for( int i = 1 ; i < sz( v ) ; i++ ){
if( v[ i ] != v[ i - 1 ] )
mpp[ v[ 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+IAojZGVmaW5lIHN6KHgpIChsbCl4LnNpemUoKQojZGVmaW5lIHN0KHgpIHNvcnQoeC5iZWdpbigpLHguZW5kKCkpCiNkZWZpbmUgcnN0KHgpIHNvcnQoeC5yYmVnaW4oKSwgeC5yZW5kKCkpCiNkZWZpbmUgYWxsKHgpIHguYmVnaW4oKSx4LmVuZCgpCmxvbmcgZG91YmxlIHBpID0gMy4xNDE1OTI2NTM1ODk3OTMyMzsKIApjb25zdCBkb3VibGUgRVBTID0gMWUtMTI7CmNvbnN0IGludCBOID0gNioxZTUgKyAxMDsKY29uc3QgaW50IG1vZCA9IDFlOSArIDc7CiAKaW50IEJJVFsgNCAqIE4gXSA7IAogCnZvaWQgdXBkYXRlKCBpbnQgcG9zLCBpbnQgdmFsICl7CiAgd2hpbGUoIHBvcyA8IE4gKXsKICAgIEJJVFsgcG9zIF0gKz0gdmFsIDsKICAgIHBvcyArPSAoIHBvcyAmIC1wb3MgKSA7CiAgfQp9CiAKaW50IHF1ZXJ5KCBpbnQgcG9zICl7CiAgaW50IGFucyggMCApIDsKICB3aGlsZSggcG9zICl7CiAgICBhbnMgKz0gQklUWyBwb3MgXSA7CiAgICBwb3MgLT0gKCBwb3MgJiAtcG9zICkgOwogIH0KICByZXR1cm4gYW5zIDsKfQogCnN0cnVjdCBxdWVyeXsKICAgY2hhciB0IDsKICAgaW50IGwsIHIgOwp9cXJyWyBOIF0gOwogCmludCBhclsgTiBdIDsKdmVjdG9yPCBpbnQgPiB2IDsKbWFwPCBpbnQsIGludCA+IG1wcCA7CiAKaW50IG1haW4oKQp7CiAgICBmYXN0OwogCiAgICBpbnQgbiwgcSA7CiAgICBjaW4gPj4gbiA+PiBxIDsKIAogICAgZm9yKCBpbnQgaSA9IDEgOyBpIDw9IG4gOyBpKysgKXsKICAgICAgY2luID4+IGFyWyBpIF0gOwogICAgICB2LnBiKCBhcltpXSApOwogICAgfQogCiAgICBmb3IoIGludCBpID0gMCA7IGkgPCBxIDsgaSsrICl7CiAgICAgIGNpbiA+PiBxcnJbIGkgXS50ID4+IHFyclsgaSBdLmwgPj4gcXJyWyBpIF0uciA7CiAgICAgICAgIHYucGIoIHFyclsgaSBdLnIgKSA7CiAgICAgICAgIHYucGIoIHFyclsgaSBdLmwgKSA7CiAgICB9CiAKICAgaW50IGluZCggMiApIDsKICAgc29ydCggYWxsKCB2ICkgKSA7CiAgIG1wcFsgdlsgMCBdIF0gPSAxIDsKICAgZm9yKCBpbnQgaSA9IDEgOyBpIDwgc3ooIHYgKSA7IGkrKyApewogICAgaWYoIHZbIGkgXSAhPSB2WyBpIC0gMSBdICkKICAgICAgbXBwWyB2WyBpIF0gXSA9IGluZCsrIDsKICAgfQogCiAgIGZvciggaW50IGkgPSAxIDsgaSA8PSBuIDsgaSsrICl7CiAgICAgIGludCBwb3MgPSBtcHBbIGFyWyBpIF0gXSA7CiAgICAgIGFyWyBpIF0gPSBwb3MgOwogICAgICB1cGRhdGUoIHBvcywgMSApIDsKICAgfQogICBmb3IoIGludCBpID0gMCA7IGkgPCBxIDsgaSsrICl7CiAgICAgIGNoYXIgdCA9IHFyclsgaSBdLnQgOwogICAgICBpbnQgbCA9IHFyclsgaSBdLmwgOwogICAgICBpbnQgciA9IHFyclsgaSBdLnIgOwogICAgICBpZiggdCA9PSAnPycgKXsKICAgICAgICAgbCA9IG1wcFsgbCBdIDsKICAgICAgICAgciA9IG1wcFsgciBdIDsKICAgICAgICAgY291dCA8PCBxdWVyeSggciApIC0gcXVlcnkoIGwgLSAxICkgPDwgJ1xuJyA7CiAgICAgIH0KICAgICAgZWxzZXsKICAgICAgICAgaW50IHByZXYgPSBhclsgbCBdIDsKICAgICAgICAgdXBkYXRlKCBwcmV2LCAtMSApIDsKICAgICAgICAgciA9IG1wcFsgciBdIDsKICAgICAgICAgdXBkYXRlKCByLCAxICkgOwogICAgICAgICBhclsgbCBdID0gciA7CiAgICAgIH0KICAgfQp9