#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,q,v=0,a[200005],bit[1000006];
pair <char,pair<int,int>> p[200005];
void UPDATE(int i, int V)
{
    while (i<=v) bit[i]+=V,i+=i&(-i);
    return;
}
int GET(int l, int r)
{
    l--;
    int resl=0,resr=0;
    while (l>0) resl+=bit[l],l-=l&(-l);
    while (r>0) resr+=bit[r],r-=r&(-r);
    return resr-resl;
}
void READINPUT()
{
    set <int> se;
    map <int,int> mp;
    cin>>n>>q;
    for (int i=1;i<=n;i++) cin>>a[i],se.insert(a[i]);
    for (int i=1;i<=q;i++)
    {
        cin>>p[i].first>>p[i].second.first>>p[i].second.second;
        if (p[i].first=='!') se.insert(p[i].second.second);
        else se.insert(p[i].second.first),se.insert(p[i].second.second);
    }
    for (int x : se) v++,mp[x]=v;
    for (int i=1;i<=n;i++) a[i]=mp[a[i]];
    for (int i=1;i<=q;i++)
    {
        if (p[i].first=='!') p[i].second.second=mp[p[i].second.second];
        else p[i].second.first=mp[p[i].second.first],p[i].second.second=mp[p[i].second.second];
    }
}
signed main()
{
    ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    READINPUT();
    for (int i=1;i<=n;i++) UPDATE(a[i],1);
    for (int i=1;i<=q;i++)
    {
        if (p[i].first=='!')
        {
            UPDATE(p[i].second.second,1);
            UPDATE(a[p[i].second.first],-1);
            a[p[i].second.first]=p[i].second.second;
        }
        else cout<<GET(p[i].second.first,p[i].second.second)<<'\n';
    }
    return 0;
}