#include<bits/stdc++.h>
using namespace std;
typedef long long int lli;
/*
#include <chrono>
using namespace std::chrono;
#include <boost/multiprecision/cpp_int.hpp>
using namespace boost::multiprecision;*/
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<pair<lli,lli>, null_type,less<pair<lli,lli>>, rb_tree_tag,tree_order_statistics_node_update>
#define endl "\n"
#define pb push_back
const lli mod=1e9+7;
const lli mod1=998244353;
#define fir first
#define sec second
#define plli pair<lli,lli>
/*
lli power(lli a, lli b) {
lli res = 1;
while (b > 0) {
if (b & 1)
res = res * a;
a = a * a;
b >>= 1;
}
return res;
}
lli powermod(lli a, lli b)
{
lli res = 1;
while (b > 0) {
if (b & 1)
res = ((res%mod)*(a%mod))%mod;
a = (a * a)%mod;
b >>= 1;
}
return res;
}
*/
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
lli T;
T=1;
while(T--)
{
ordered_set s;
lli n,q;
cin>>n>>q;
lli a[n+1],i;
for(i=1;i<=n;i++)
{
cin>>a[i];
s.insert({a[i],i});
}
char x;
lli y,z;
while(q--)
{
cin>>x>>y>>z;
if(x=='!')
{
s.erase({a[y],y});
a[y]=z;
s.insert({a[y],y});
}
else
{
lli l=s.order_of_key({y,0});
lli r=s.order_of_key({z,n+1});
/*for(auto it:s)
cout<<it.fir<<" "<<it.sec<<"\n";*/
cout<<r-l<<"\n";
}
}
}
return 0;
}
I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKdHlwZWRlZiBsb25nIGxvbmcgaW50IGxsaTsKLyoKI2luY2x1ZGUgPGNocm9ubz4gCnVzaW5nIG5hbWVzcGFjZSBzdGQ6OmNocm9ubzsKI2luY2x1ZGUgPGJvb3N0L211bHRpcHJlY2lzaW9uL2NwcF9pbnQuaHBwPiAKdXNpbmcgbmFtZXNwYWNlIGJvb3N0OjptdWx0aXByZWNpc2lvbjsqLwojaW5jbHVkZSA8ZXh0L3BiX2RzL2Fzc29jX2NvbnRhaW5lci5ocHA+IAojaW5jbHVkZSA8ZXh0L3BiX2RzL3RyZWVfcG9saWN5LmhwcD4gCnVzaW5nIG5hbWVzcGFjZSBfX2dudV9wYmRzOyAKI2RlZmluZSBvcmRlcmVkX3NldCB0cmVlPHBhaXI8bGxpLGxsaT4sIG51bGxfdHlwZSxsZXNzPHBhaXI8bGxpLGxsaT4+LCByYl90cmVlX3RhZyx0cmVlX29yZGVyX3N0YXRpc3RpY3Nfbm9kZV91cGRhdGU+IAogCiNkZWZpbmUgZW5kbCAiXG4iCiNkZWZpbmUgcGIgcHVzaF9iYWNrCmNvbnN0IGxsaSBtb2Q9MWU5Kzc7CmNvbnN0IGxsaSBtb2QxPTk5ODI0NDM1MzsKI2RlZmluZSBmaXIgZmlyc3QKI2RlZmluZSBzZWMgc2Vjb25kCiNkZWZpbmUgcGxsaSBwYWlyPGxsaSxsbGk+Ci8qCmxsaSBwb3dlcihsbGkgYSwgbGxpIGIpIHsKICAgIGxsaSByZXMgPSAxOwogICAgd2hpbGUgKGIgPiAwKSB7CiAgICAgICAgaWYgKGIgJiAxKQogICAgICAgICAgICByZXMgPSByZXMgKiBhOwogICAgICAgIGEgPSBhICogYTsKICAgICAgICBiID4+PSAxOwogICAgfQogICAgcmV0dXJuIHJlczsKfQpsbGkgcG93ZXJtb2QobGxpIGEsIGxsaSBiKSAKewogICAgbGxpIHJlcyA9IDE7CiAgICB3aGlsZSAoYiA+IDApIHsKICAgICAgICBpZiAoYiAmIDEpCiAgICAgICAgICAgIHJlcyA9ICgocmVzJW1vZCkqKGElbW9kKSklbW9kOwogICAgICAgIGEgPSAoYSAqIGEpJW1vZDsKICAgICAgICBiID4+PSAxOwogICAgfQogICAgcmV0dXJuIHJlczsKfQoqLwppbnQgbWFpbigpCnsKICAgIGlvc19iYXNlOjpzeW5jX3dpdGhfc3RkaW8oZmFsc2UpOwogICAgY2luLnRpZShOVUxMKTsKICAgIGxsaSBUOwogICAgVD0xOwogICAgd2hpbGUoVC0tKQogICAgewogICAgICAgIG9yZGVyZWRfc2V0IHM7CiAgICAgICAgbGxpIG4scTsKICAgICAgICBjaW4+Pm4+PnE7CiAgICAgICAgbGxpIGFbbisxXSxpOwogICAgICAgIGZvcihpPTE7aTw9bjtpKyspCiAgICAgICAgewogICAgICAgICAgICBjaW4+PmFbaV07CiAgICAgICAgICAgIHMuaW5zZXJ0KHthW2ldLGl9KTsKICAgICAgICB9CiAgICAgICAgY2hhciB4OwogICAgICAgIGxsaSB5LHo7CiAgICAgICAgd2hpbGUocS0tKQogICAgICAgIHsKICAgICAgICAgICAgY2luPj54Pj55Pj56OwogICAgICAgICAgICBpZih4PT0nIScpCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIHMuZXJhc2Uoe2FbeV0seX0pOwogICAgICAgICAgICAgICAgYVt5XT16OwogICAgICAgICAgICAgICAgcy5pbnNlcnQoe2FbeV0seX0pOwogICAgICAgICAgICB9CiAgICAgICAgICAgIGVsc2UKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgbGxpIGw9cy5vcmRlcl9vZl9rZXkoe3ksMH0pOwogICAgICAgICAgICAgICAgbGxpIHI9cy5vcmRlcl9vZl9rZXkoe3osbisxfSk7CiAgICAgICAgICAgICAgICAvKmZvcihhdXRvIGl0OnMpCiAgICAgICAgICAgICAgICAgICAgY291dDw8aXQuZmlyPDwiICI8PGl0LnNlYzw8IlxuIjsqLwogICAgICAgICAgICAgICAgY291dDw8ci1sPDwiXG4iOwogICAgICAgICAgICB9CiAgICAgICAgfQogCiAgICB9ICAgIAogICAgcmV0dXJuIDA7Cn0KIAogCiAKIAog