#include <bits/stdc++.h>
using namespace std;
 
const int maxN=2e5;
int bit[maxN*3+1];//  紀錄每個薪水的數量
int arr[maxN];
struct Data{
	char c;
	int a, b;
}dt[maxN];
vector<int> v; // 離散化
int N, Q;
 
void update(int x,int v){
	for(; x<=maxN*3;x+=(x&(-x)) )
		bit[x]+=v;
}
int query(int x){
	int ans=0;
	for(; x>0;x-=(x&(-x)) )
		ans+=bit[x];
	return ans;	
}
 
int main() {
	cin>>N>>Q;
	for(int i=0;i<=maxN*3;i++)
		bit[i]=0;
 
	for(int i=0;i<N;i++){
		cin>>arr[i];
		v.push_back(arr[i]);
	}
 
	for(int i=0;i<Q;i++){
		cin>>dt[i].c>>dt[i].a>>dt[i].b;
		if( dt[i].c=='!' )
			v.push_back(dt[i].b);
		else{
			v.push_back(dt[i].a);
			v.push_back(dt[i].b);
		}
	}
	v.push_back(-1);
	sort(v.begin(),v.end() );
	v.erase( unique(v.begin(),v.end()),v.end() );
 
	for(int i=0;i<N;i++){
		int p=lower_bound(v.begin(),v.end(),arr[i])-v.begin();
		update(p,1);
	}
 
	for(int i=0;i<Q;i++){
		if( dt[i].c=='?' ){
			int p1=lower_bound(v.begin(),v.end(),dt[i].a)-v.begin();
			int p2=lower_bound(v.begin(),v.end(),dt[i].b)-v.begin();
			cout<<query(p2)-query(p1-1)<<'\n';
		}
		else{
			int p1=lower_bound(v.begin(),v.end(),arr[dt[i].a-1])-v.begin();
			int p2=lower_bound(v.begin(),v.end(),dt[i].b)-v.begin();
			arr[dt[i].a-1]=dt[i].b;
			update(p1,-1);
			update(p2,1);
		}	
	}
}

I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7Cgpjb25zdCBpbnQgbWF4Tj0yZTU7CmludCBiaXRbbWF4TiozKzFdOy8vICDntIDpjITmr4/lgIvolqrmsLTnmoTmlbjph48KaW50IGFyclttYXhOXTsKc3RydWN0IERhdGF7CgljaGFyIGM7CglpbnQgYSwgYjsKfWR0W21heE5dOwp2ZWN0b3I8aW50PiB2OyAvLyDpm6LmlaPljJYKaW50IE4sIFE7Cgp2b2lkIHVwZGF0ZShpbnQgeCxpbnQgdil7Cglmb3IoOyB4PD1tYXhOKjM7eCs9KHgmKC14KSkgKQoJCWJpdFt4XSs9djsKfQppbnQgcXVlcnkoaW50IHgpewoJaW50IGFucz0wOwoJZm9yKDsgeD4wO3gtPSh4JigteCkpICkKCQlhbnMrPWJpdFt4XTsKCXJldHVybiBhbnM7CQp9CgppbnQgbWFpbigpIHsKCWNpbj4+Tj4+UTsKCWZvcihpbnQgaT0wO2k8PW1heE4qMztpKyspCgkJYml0W2ldPTA7CgkKCWZvcihpbnQgaT0wO2k8TjtpKyspewoJCWNpbj4+YXJyW2ldOwoJCXYucHVzaF9iYWNrKGFycltpXSk7Cgl9CgkKCWZvcihpbnQgaT0wO2k8UTtpKyspewoJCWNpbj4+ZHRbaV0uYz4+ZHRbaV0uYT4+ZHRbaV0uYjsKCQlpZiggZHRbaV0uYz09JyEnICkKCQkJdi5wdXNoX2JhY2soZHRbaV0uYik7CgkJZWxzZXsKCQkJdi5wdXNoX2JhY2soZHRbaV0uYSk7CgkJCXYucHVzaF9iYWNrKGR0W2ldLmIpOwoJCX0KCX0KCXYucHVzaF9iYWNrKC0xKTsKCXNvcnQodi5iZWdpbigpLHYuZW5kKCkgKTsKCXYuZXJhc2UoIHVuaXF1ZSh2LmJlZ2luKCksdi5lbmQoKSksdi5lbmQoKSApOwoJCglmb3IoaW50IGk9MDtpPE47aSsrKXsKCQlpbnQgcD1sb3dlcl9ib3VuZCh2LmJlZ2luKCksdi5lbmQoKSxhcnJbaV0pLXYuYmVnaW4oKTsKCQl1cGRhdGUocCwxKTsKCX0KCQoJZm9yKGludCBpPTA7aTxRO2krKyl7CgkJaWYoIGR0W2ldLmM9PSc/JyApewoJCQlpbnQgcDE9bG93ZXJfYm91bmQodi5iZWdpbigpLHYuZW5kKCksZHRbaV0uYSktdi5iZWdpbigpOwoJCQlpbnQgcDI9bG93ZXJfYm91bmQodi5iZWdpbigpLHYuZW5kKCksZHRbaV0uYiktdi5iZWdpbigpOwoJCQljb3V0PDxxdWVyeShwMiktcXVlcnkocDEtMSk8PCdcbic7CgkJfQoJCWVsc2V7CgkJCWludCBwMT1sb3dlcl9ib3VuZCh2LmJlZ2luKCksdi5lbmQoKSxhcnJbZHRbaV0uYS0xXSktdi5iZWdpbigpOwoJCQlpbnQgcDI9bG93ZXJfYm91bmQodi5iZWdpbigpLHYuZW5kKCksZHRbaV0uYiktdi5iZWdpbigpOwoJCQlhcnJbZHRbaV0uYS0xXT1kdFtpXS5iOwoJCQl1cGRhdGUocDEsLTEpOwoJCQl1cGRhdGUocDIsMSk7CgkJfQkKCX0KfQ==

MTAgMTAKOSA5IDEgNCAzIDIgMTAgMSAyIDEKPyAxIDUKPyAzIDkKPyAyIDUKISA1IDEKPyAyIDUKPyAyIDQKPyAzIDEwCj8gMiA2Cj8gNyA3Cj8gMyA3

10 10
9 9 1 4 3 2 10 1 2 1
? 1 5
? 3 9
? 2 5
! 5 1
? 2 5
? 2 4
? 3 10
? 2 6
? 7 7
? 3 7