#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
	cin.tie(0);
	ios_base::sync_with_stdio(0);
	
	int n, q;
	cin >> n >> q;
	vector<int> p(n);
	vector<tuple<char, int, int>> queries;
	vector<int> val_set;
	
	for(int i = 0; i < n; i++){
		cin >> p[i];
		val_set.push_back(p[i]);
	}
	
	for(int i = 0; i < q; i++){
		char op;
		int a, b;
		cin >> op >> a >> b;
		if(op == '?') val_set.push_back(a);
		else a--;
		val_set.push_back(b);
		queries.push_back({op, a, b});
	}
	
	sort(val_set.begin(), val_set.end());
	val_set.resize(unique(val_set.begin(), val_set.end()) - val_set.begin());
	
	for(auto &p_val: p){
		p_val = lower_bound(val_set.begin(), val_set.end(), p_val) - val_set.begin();
	}
	for(auto &[op, a, b]: queries){
		if(op == '?') a = lower_bound(val_set.begin(), val_set.end(), a) - val_set.begin();
		b = lower_bound(val_set.begin(), val_set.end(), b) - val_set.begin();
	}
	
	vector<int> BITS(val_set.size() + 1);
	auto update = [&BITS](int pos, int val){
		while(pos < BITS.size()){
			BITS[pos] += val;
			pos += pos & -pos;
		}
	};
	auto query = [&BITS](int pos){
		int ans = 0;
		while(pos){
			ans += BITS[pos];
			pos -= pos & -pos;
		}
		return ans;
	};
	
	for(auto &p_val: p){
		update(p_val + 1, 1);
	}
	
	for(auto &[op, a, b]: queries){
		if(op == '?') cout << query(b + 1) - query(a) << '\n';
		else{
			update(p[a] + 1, -1);
			p[a] = b;
			update(p[a] + 1, 1);
		}
	}
	return 0;
}