#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define gc getchar
#define pb push_back
#define eb emplace_back
#define all(x) (x).begin(),(x).end()
#define x1 uvuvwe
#define y1 onyetvwe
#define x2 onyette
#define y2 ugmewuben
typedef long long LL;
typedef long double LD;
typedef pair<int,int> pii;
const int treesize=262144;
const int INF=1000000;
template <typename T> void scan(T &angka){
	angka=0;char input=gc();T kali=1;
	while(!(48<=input&&input<=57)){	if(input=='-')	kali=-1;input=gc();}
	while(48<=input&&input<=57)	angka=(angka<<3)+(angka<<1)+input-48,input=gc();angka*=kali;
}
template <typename T1,typename T2> void scan(T1 &angka1,T2 &angka2){
	scan(angka1);scan(angka2);
}
int n,m,arr[200005],occ[200005]={},currans=0,lebih[200005]={};
int tree[treesize*2+5],lazy[treesize*2+5]={};
bool debug=false;
void hitungans(){
	int _lebih=0;
	occ[0]=INF;			//kasi INF
	for(int i=n;i>=0;i--)
	{
		lebih[i]=_lebih;
		currans+=min(lebih[i],occ[i]);			//salah satunya di buang
		_lebih=max(lebih[i],occ[i]);
		if(_lebih>0)
			_lebih--;
	}
}
void pullup(int indeks){
	tree[indeks]=min(tree[indeks<<1],tree[(indeks<<1)|1]);
}
void pushdown(int indeks){
	if(lazy[indeks]==0)
		return;
	tree[indeks<<1]+=lazy[indeks];
	lazy[indeks<<1]+=lazy[indeks];
	tree[(indeks<<1)+1]+=lazy[indeks];
	lazy[(indeks<<1)+1]+=lazy[indeks];
	lazy[indeks]=0;
}
void buat(int kiri,int kanan,int indeks){
	if(kiri==kanan)
	{
		tree[indeks]=lebih[kiri]-occ[kiri];
		return;
	}
	int mid=(kiri+kanan)>>1;
	buat(kiri,mid,indeks<<1);
	buat(mid+1,kanan,(indeks<<1)+1);
	pullup(indeks);
}
void update(int kiri,int kanan,int indeks,int l,int r,int tambah){
	if(l<=kiri&&kanan<=r)
	{
		lazy[indeks]+=tambah;
		tree[indeks]+=tambah;
		return;
	}
	if(l>kanan||r<kiri)
		return;
	int mid=(kiri+kanan)>>1;
	pushdown(indeks);
	update(kiri,mid,indeks<<1,l,r,tambah);
	update(mid+1,kanan,(indeks<<1)+1,l,r,tambah);
	pullup(indeks);
}
int query(int kiri,int kanan,int indeks,int l,int r){
	if(l<=kiri&&kanan<=r)
		return tree[indeks];
	if(l>kanan||r<kiri)
		return INF;
	int mid=(kiri+kanan)>>1;
	pushdown(indeks);
	return min(query(kiri,mid,indeks<<1,l,r),query(mid+1,kanan,(indeks<<1)+1,l,r));
}
void updateans(int value,int tambah){
	//if(debug) cout<<"untuk "<<value<<" "<<tambah<<endl;
	update(0,n,1,value,value,-tambah);
	//return;
	//cout<<query(0,n,1,value,value)<<" "<<batas<<endl;
	if(query(0,n,1,value,value)+min(0,tambah)>=0)
	{
		//if(debug)	cout<<"ditambah "<<tambah<<endl;
		currans+=tambah;			//tandanya sudah jelas dia dak dipake
		return;
	}
	int bataskiri=max(value-occ[value]+((tambah==1)?1:0),0);
	//if(debug)	cout<<"bataskirinya "<<bataskiri<<endl;
	int bawah=bataskiri,atas=value-1,mid;
	while(bawah<=atas)
	{
		mid=(bawah+atas)>>1;
		if(query(0,n,1,mid,value-1)+max(tambah,0)<=0)			//berarti dak perlu di update, sampai di titik sini boleh berhenti
			bawah=mid+1;
		else
			atas=mid-1;
	}
	//if(debug)	cout<<"after binser "<<bawah<<" "<<atas<<endl;
	//if(debug) cout<<"posisi di mana updatenya terakhir "<<atas<<endl;
	if(atas>=bataskiri)
	{
		currans+=tambah;
		//if(debug)	cout<<"ditambah "<<tambah<<endl;
	}
	atas=max(atas,bataskiri);
	if(atas<=value-1)
		update(0,n,1,atas,value-1,tambah);
}
void printarr(){
	cout<<"printing occ"<<endl;
	for(int i=0;i<=n;i++)
		cout<<occ[i]<<"\t";
	cout<<endl;
	cout<<"printing lebih"<<endl;
	for(int i=0;i<=n;i++)
		cout<<query(0,n,1,i,i)+occ[i]<<"\t";
	cout<<endl;;
}
int main()
{
	scan(n,m);
	for(int i=1;i<=n;i++)
	{
		scan(arr[i]);
		occ[arr[i]]++;
	}
	hitungans();
	buat(0,n,1);
	//printarr();
	//return 0;
	for(int ulang=1;ulang<=m;ulang++)
	{
		//debug=(ulang==2);
		int pos,nilai;
		scan(pos,nilai);
		occ[nilai]++;
		updateans(nilai,1);
		occ[arr[pos]]--;
		updateans(arr[pos],-1);
		arr[pos]=nilai;
		printf("%d\n",currans);
		//if(debug)	printarr();
	}
}

Measured memory_bytes: 7936