#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;
}