#include <bits/stdc++.h>
using namespace std;

#define bolt_io ios_base::sync_with_stdio(0), cin.tie(0)

const int N = 6e5 + 5;
int n, q, uc, n_, ic, st[4 * N], a[N], b[N];
vector<tuple<char, int, int>> vp;
map<int, int> mp;

void f1(int sti, int ll, int rr, int ix, int v)
{
    if (ll == rr)
        st[sti] += v;
    else
    {
        int m = (ll + rr) >> 1;
        if (ix <= m)
            f1(2 * sti + 1, ll, m, ix, v);
        else
            f1(2 * sti + 2, m + 1, rr, ix, v);

        st[sti] += v;
    }
}

int f2(int sti, int ll, int rr, int lq, int rq)
{
    if (rq < ll || rr < lq)
        return 0;
    else if (lq <= ll && rr <= rq)
        return st[sti];
    else
    {
        int m = (ll + rr) >> 1;
        return f2(2 * sti + 1, ll, m, lq, rq) + f2(2 * sti + 2, m + 1, rr, lq, rq);
    }
}

signed main()
{
    bolt_io;
    cin >> n >> q;
    for (int i = 0; i < n; i++)
        cin >> a[ic], ic++;

    vp.resize(q);
    for (int i = 0; i < q; i++)
    {
        char ch;
        int x, y;
        cin >> ch >> x >> y;
        vp[i] = {ch, x, y};

        if (ch == '!')
            a[ic] = y, ic++;
        else
            a[ic] = x, a[ic + 1] = y, ic += 2;
    }

    for (int i = 0; i < n; i++)
        b[i] = a[i];

    sort(a, a + ic);
    mp[a[0]] = 0;

    for (int i = 1; i < ic; i++)
        if (a[i] != a[i - 1])
            mp[a[i]] = mp[a[i - 1]] + 1;

    uc = mp.size();
    n_ = 1 << (__lg(uc) + 1);
    if ((uc & (uc - 1)) == 0)
        n_ >>= 1;

    for (int i = 0; i < n; i++)
        f1(0, 0, n_ - 1, mp[b[i]], +1);

    for (tuple<char, int, int> entry : vp)
    {
        if (get<0>(entry) == '!')
        {
            f1(0, 0, n_ - 1, mp[b[get<1>(entry)] - 1], -1);
            b[get<1>(entry) - 1] = get<2>(entry);
            f1(0, 0, n_ - 1, mp[b[get<1>(entry) - 1]], +1);
        }
        else
        {
            cout << f2(0, 0, n_ - 1, mp[get<1>(entry)], mp[get<2>(entry)]) << ' ';
        }
    }

    return 0;
}