#include <bits/stdc++.h>
using namespace std;
int n, _n, q;
int a[200005];
int st[4 * 800005];
vector <int> vt;
unordered_map <int, int> h;

struct ZATA {
    char d;
    int l, r;
} ques[200005];

void upd(int id, int l, int r, int pos, int val) {
    if (l > pos || r < pos) return;
    if (l == r) {
        st[id] += val;
        return;
    }
    int mid = (l + r) / 2;
    upd(id * 2, l, mid, pos, val);
    upd(id * 2 + 1, mid + 1, r, pos, val);
    st[id] = st[id * 2] + st[id * 2 + 1];
}

int get(int id, int l, int r, int u, int v) {
    if (l > v || r < u) return 0;
    if (l >= u && r <= v) return st[id];
    int mid = (l + r) / 2;
    return get(id * 2, l, mid, u, v) + get(id * 2 + 1, mid + 1, r, u, v);
}

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        vt.push_back(a[i]);
    }
    for (int i = 1; i <= q; i++) {
        cin >> ques[i].d >> ques[i].l >> ques[i].r;
        if (ques[i].d == '!') {
            vt.push_back(ques[i].r);
        } else {
            vt.push_back(ques[i].l);
            vt.push_back(ques[i].r);
        }
    }

    sort(vt.begin(), vt.end());
    vt.erase(unique(vt.begin(), vt.end()), vt.end());
    _n = vt.size();
    for (int j = 0; j < _n; j++) h[vt[j]] = j + 1;
    for (int i = 1; i <= n; i++) {
        a[i] = h[a[i]];
        upd(1, 1, _n, a[i], 1);
    }

    for (int i = 1; i <= q; i++) {
        if (ques[i].d == '!') {
            int k = ques[i].l;
            int x = h[ques[i].r];
            upd(1, 1, _n, a[k], -1);
            a[k] = x;
            upd(1, 1, _n, x, 1);
        } else {
            int l = h[ques[i].l];
            int r = h[ques[i].r];

            cout << get(1, 1, _n, l, r) << '\n';

        }
    }

    return 0;
}