#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define pb push_back
#define INF 0x3f3f3f3
#define LINF 0x3f3f3f3f3f3f3f
#define MAXN 2*int(1e5)+7
#define fim '\n'
#define ll long long
#define f first
#define s second
#define FAST cin.tie(0), cout.tie(0), ios::sync_with_stdio(0)
#define debug(x) cout << "DEBUG " << x << fim
#define debug2(x, y) cout << "DEBUG " << x << " " << y << fim
#define debug3(x, y, z) cout << "DEBUG " << x << " " << y << " " << z<< fim
#define max3(x, y, z) max(x, max(y, z))
using namespace std;
using namespace __gnu_pbds;
typedef pair<int, int> pii;
typedef pair<string, int> psi;
typedef pair<unsigned ll, pair<int, int> > piii;
typedef pair<pair<int, int>, int> piii2;
typedef pair<char, pair<int, int>> pcii;
typedef tree<int,null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> indexed_set;

int n, q, bit[MAXN], vet[MAXN];
vector<pcii> queries;
unordered_map<int, int> val;

void update(int i, int x) {
    while(i <= n) {
        bit[i] += x;
        i += i & -i;
    }
    return;
}

int query(int i) {
    int soma = 0;
    while(i > 0) {
        soma += bit[i];
        i -= i & -i;
    }
    return soma;
}

int main() {

    FAST;
    cin >> n >> q;
    vector<int> numbers;

    for(int i = 1; i <= n; numbers.pb(vet[i]), i++)
        cin >> vet[i];

    while(q--) {
        char c;
        int a, b;
        cin >> c >> a >> b;
        if(c == '!')
            numbers.pb(b);
        else {
            numbers.pb(a);
            numbers.pb(b);
        }
        queries.pb({c, {a, b}});
    }

    sort(numbers.begin(), numbers.end());

    int cont = 0;
    for(auto i : numbers) {
        if(val[i]) continue;
        val[i] = ++cont;
    }

    for(int i = 1; i <= n; i++)
        update(val[vet[i]], 1);

    for(auto i : queries) {
        if(i.f == '?')
            cout << query(val[i.s.s])-query(val[i.s.f]-1) << endl;
        else {
            update(val[vet[i.s.f]], -1);
            update(val[i.s.s], 1);
            vet[i.s.f] = i.s.s;
        }
    }
}