#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;
using namespace chrono;

#define mod 1000000007
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define pii pair<int, int>
#define vb vector<bool>
#define int long long
#define ld long double
#define vi vector<int>
#define vvi vector<vector<int>>
#define vvc vector<vector<char>>
#define vll vector<long long>
#define vc vector<char>
#define vs vector<string>
#define s string
#define all(x) (x).begin(), (x).end()
#define cneg cout << -1 << endl;
#define fastio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

void print(auto a)
{
  for (auto i : a)
  {
    cout << i.ff << " ";
  }
  cout << endl;
}

template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
// order_of_key (k) : Number of items strictly smaller than k

class STree
{
  int sz;
  vector<ordered_set<pii>> vals;
  int cnt = 0;

  void _print()
  {
    for(auto i : vals)
    {
      print(i);
    }
  }

  ordered_set<pii> expr(int x)
  {
    auto st = vals[2*x + 1];
    for(auto i : vals[2*x + 2])
    {
      st.insert(i);
    }
    return st; // CHANGE THIS FOR OTHER USES
  }

  void build(vi& a, int x, int lx, int rx)
  {
    if(rx - lx == 1) // leaf node
    {
      if(lx < (int)a.size())
      {
        vals[x].insert({a[lx], cnt++});
      }
      return;
    }
    int m = lx + (rx - lx)/2;

    build(a, 2*x + 1, lx, m);
    build(a, 2*x + 2, m, rx);

    vals[x] = expr(x);
  }

  pii set(int i, int v, int x, int lx, int rx)
  {
    if(rx - lx == 1)
    {
      pii ele = *vals[x].begin();
      vals[x].erase(ele);
      vals[x].insert({v, ele.ss});
      return ele;
    }
    int m = lx + (rx - lx)/2;

    if(i < m)
    {
      pii c = set(i, v, 2*x + 1, lx, m);
      vals[x].erase(c);
      vals[x].insert({v, c.ss});

      return c;
    }

    pii c = set(i, v, 2*x + 2, m, rx);
    vals[x].erase(c);
    vals[x].insert({v, c.ss});

    return c;
  }

  int _query(int l, int r)
  {
    auto itrL = vals[0].lower_bound({l, 0ll});
    if(itrL == vals[0].end()) return 0;

    int cntLessL = vals[0].order_of_key(*itrL);

    auto itrR = vals[0].upper_bound({r, LLONG_MAX});
    if(itrR == vals[0].end()) return vals[0].size() - cntLessL;

    int cntLessR = vals[0].order_of_key(*itrR);

    return cntLessR - cntLessL;
  }
public:
  STree(vi& a)
  {
    int n = a.size();

    sz = 1;

    while(sz < n) sz <<= 1;

    vals.assign(2*sz, ordered_set<pii>());

    build(a);
  }

  void build(vi& a)
  {
    build(a, 0, 0, sz);
  }

  void set(int i, int v) // sets ith value (0-indexed) to v
  {
    set(i, v, 0, 0, sz);
  }

  void _printT()
  {
    _print();
  }

  int query(int l, int r) // range is [l, r]
  {
    return _query(l, r);
  }
};

void solve()
{
  int n, m;
  cin >> n >> m;

  vi a(n);
  ordered_set<pii> st;
  for (int i = 0; i < n; i++)
  {
    cin >> a[i];
    st.insert({a[i], i});
  }

  // STree sgt(a);

  for(int i = 0; i < m; i++)
  {
    char ch;
    cin >> ch;

    if(ch == '?')
    {
      int l, r;
      cin >> l >> r;

      auto itrL = st.lower_bound({l, 0});

      if(itrL == st.end())
      {
        cout << 0 << endl;
        continue;
      }

      auto itrR = st.upper_bound({r, INT_MAX});

      if(itrR == st.end())
      {
        cout << n - st.order_of_key(*itrL) << endl;
        continue;
      }

      cout << st.order_of_key(*itrR) - st.order_of_key(*itrL) << endl;
    }
    else
    {
      int k, x;
      cin >> k >> x;

      st.erase({a[k - 1], k - 1});
      st.insert({x, k - 1});
      a[k - 1] = x;
    }
  }
}

#undef int
int main()
{
#ifndef ONLINE_JUDGE
  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);
  freopen("error.txt", "w", stderr);
#endif
  fastio();

  auto start1 = high_resolution_clock::now();

  int t = 1;
  // cin >> t;

  while (t--)
  {
    solve();
  }

  auto stop1 = high_resolution_clock::now();
  auto duration = duration_cast<milliseconds>(stop1 - start1);
#ifndef ONLINE_JUDGE
  cerr << "Time: " << duration.count() << " ms" << endl;
#endif

  return 0;
}