stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#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;

 

#define fi first

#define se second

#define mp make_pair

#define pb push_back

#define fbo find_by_order

#define ook order_of_key

 

typedef long long ll;

typedef pair<int,int> ii;

typedef vector<int> vi;

typedef long double ld; 

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;

typedef set<int>::iterator sit;

typedef map<int,int>::iterator mit;

typedef vector<int>::iterator vit;



int cnt[211111]; //counts how many times the interval [i,i+1) is covered. we want cnt[0],cnt[1],...,cnt[n-1] = 1

int cov[211111];

int a[211111];



int main()

{

	ios_base::sync_with_stdio(0); cin.tie(0);

	int n,m; cin>>n>>m;

	for(int i=1;i<=n;i++) cov[i]=i-1;

	int res=n;

	for(int i = 0; i < n; i++)

	{

		int x; cin>>x;

		a[i]=x;

		if(cov[x]>=0) 

		{

			if(cnt[cov[x]]==0) res--;

			cnt[cov[x]]++;

		}

		cov[x]--;

	}

	for(int i = 0; i < m; i++)

	{

		int x, y; cin>>x>>y;

		x--;

		cov[a[x]]++;

		if(cov[a[x]]>=0)

		{

			if(cnt[cov[a[x]]]==1) res++;

			cnt[cov[a[x]]]--;

		}

		if(cov[y]>=0)

		{

			if(cnt[cov[y]]==0) res--;

			cnt[cov[y]]++;

		}

		cov[y]--;

		a[x]=y;

		cout<<res<<'\n';

	}

}


// Faster C++ solution for the same problem (measured speedup: 5.168289842834631x):
#include<cstdio>

#include<algorithm>

using namespace std;



const int MAXN=2e5 + 100;

typedef pair<int,int> pii;

#define fi first

#define se second



int n,m;

pii q[MAXN];

int cnt[MAXN],f[MAXN],a[MAXN];



int main(){

    scanf("%d%d",&n,&m);

    for(int i=1;i<=n;i++) scanf("%d",&a[i]);

    for(int i=1;i<=m;i++) scanf("%d%d",&q[i].fi,&q[i].se);

    for(int i=1;i<=n;i++) cnt[a[i]]++;

    for(int i=1;i<=n;i++){

        if(cnt[i])

            for(int j=max(0,i-cnt[i]);j<i;j++)

                f[j]++;

    }

    int ans=0;

    for(int i=0;i<n;i++) if(!f[i]) ans++;

    for(int i=1;i<=m;i++){

        int x=a[q[i].fi],y=q[i].se;

        a[q[i].fi]=y;

        if(x-cnt[x]>=0){

            f[x-cnt[x]]--;

            if(f[x-cnt[x]]==0) ans++;

        }

        cnt[x]--;

        if(y-cnt[y]-1>=0){

            f[y-cnt[y]-1]++;

            if(f[y-cnt[y]-1]==1) ans--;

        }

        cnt[y]++;

        printf("%d\n",ans);

    }

}
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;



typedef long long ll;

typedef pair<int, int> ii; 



const int N = 2e5 + 10; 

int n, m, a[N], cnt[N], p[N], tot;  



void add(int x) {

    int l = x - cnt[x]++; 

    if(l > 0 && ++p[l] == 1) 

        --tot; 

}

void rem(int x) {

    int l = x - --cnt[x]; 

    if(l > 0 && --p[l] == 0) 

        ++tot;

}



int main(int argc, char const *argv[]) {

    scanf("%d %d", &n, &m);

    for(int i = 1; i <= n; i++) {

        scanf("%d", &a[i]);

        add(a[i]); 

    } tot += n;  

    while(m--) {

        int x, y; 

        scanf("%d %d", &x, &y);

        rem(a[x]); a[x] = y; add(a[x]); 

        printf("%d\n", tot); 

    }

}


// Faster C++ solution for the same problem (measured speedup: 5.050745374841512x):
#include<cstdio>

#include<algorithm>

using namespace std;



const int MAXN=2e5 + 100;

typedef pair<int,int> pii;

#define fi first

#define se second



int n,m;

pii q[MAXN];

int cnt[MAXN],f[MAXN],a[MAXN];



int main(){

    scanf("%d%d",&n,&m);

    for(int i=1;i<=n;i++) scanf("%d",&a[i]);

    for(int i=1;i<=m;i++) scanf("%d%d",&q[i].fi,&q[i].se);

    for(int i=1;i<=n;i++) cnt[a[i]]++;

    for(int i=1;i<=n;i++){

        if(cnt[i])

            for(int j=max(0,i-cnt[i]);j<i;j++)

                f[j]++;

    }

    int ans=0;

    for(int i=0;i<n;i++) if(!f[i]) ans++;

    for(int i=1;i<=m;i++){

        int x=a[q[i].fi],y=q[i].se;

        a[q[i].fi]=y;

        if(x-cnt[x]>=0){

            f[x-cnt[x]]--;

            if(f[x-cnt[x]]==0) ans++;

        }

        cnt[x]--;

        if(y-cnt[y]-1>=0){

            f[y-cnt[y]-1]++;

            if(f[y-cnt[y]-1]==1) ans--;

        }

        cnt[y]++;

        printf("%d\n",ans);

    }

}
// Slower C++ solution:
#include <bits/stdc++.h>

 

using namespace std;

 

int n, m, x[200005], ca[200005], cb[200005], ans, ta, tb, tc;

 

int main() {

	scanf("%d%d", &n, &m);

	for (int i = 1; i <= n; i++) {

		scanf("%d", x + i);

		ta = max(0, x[i] - ca[x[i]]);

		ca[x[i]]++;

		cb[ta]++;

	}

	for (int i = 1; i <= n; i++)

		ans += (cb[i] == 0);

	while (m--) {

		scanf("%d%d", &ta, &tb);

		ca[x[ta]]--;

		tc = max(0, x[ta] - ca[x[ta]]);

		cb[tc]--;

		if (tc && !cb[tc])

			ans++;

		x[ta] = tb;

		tc = max(0, x[ta] - ca[x[ta]]);

		ca[x[ta]]++;

		if (tc && !cb[tc])

			ans--;

		cb[tc]++;

		printf("%d\n", ans);

	}

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.098732665238868x):
#include<cstdio>

#include<algorithm>

using namespace std;

#define MAXN 200010

int cnt[MAXN],a[MAXN],A[MAXN];

int n,m,x,y,ans;

int main()

{

	scanf("%d%d",&n,&m);

	for(int i=1;i<=n;i++)

	{

		scanf("%d",&A[i]);

		a[max(0,A[i]-cnt[A[i]])]++;

		cnt[A[i]]++;

	}

	for(int i=1;i<=n;i++)

		if(!a[i]) ans++;

	while(m--)

	{

		scanf("%d%d",&x,&y);

		int k=max(0,A[x]-cnt[A[x]]+1);

		if(k&&a[k]==1) ans++;

		a[k]--;

		cnt[A[x]]--;

		A[x]=y;

		k=max(0,A[x]-cnt[A[x]]);

		if(k&&a[k]==0) ans--;

		a[k]++;

		cnt[A[x]]++;

		printf("%d\n",ans);

	}

}
// Slower C++ solution:
#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;

 

#define fi first

#define se second

#define mp make_pair

#define pb push_back

#define fbo find_by_order

#define ook order_of_key

 

typedef long long ll;

typedef pair<int,int> ii;

typedef vector<int> vi;

typedef long double ld; 

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;

typedef set<int>::iterator sit;

typedef map<int,int>::iterator mit;

typedef vector<int>::iterator vit;



int cnt[211111]; //counts how many times the interval [i,i+1) is covered. we want cnt[0],cnt[1],...,cnt[n-1] = 1

int cov[211111];

int a[211111];



int main()

{

	ios_base::sync_with_stdio(0); cin.tie(0);

	int n,m; cin>>n>>m;

	for(int i=1;i<=n;i++) cov[i]=i-1;

	int res=n;

	for(int i = 0; i < n; i++)

	{

		int x; cin>>x;

		a[i]=x;

		if(cov[x]>=0) 

		{

			if(cnt[cov[x]]==0) res--;

			cnt[cov[x]]++;

		}

		cov[x]--;

	}

	for(int i = 0; i < m; i++)

	{

		int x, y; cin>>x>>y;

		x--;

		cov[a[x]]++;

		if(cov[a[x]]>=0)

		{

			if(cnt[cov[a[x]]]==1) res++;

			cnt[cov[a[x]]]--;

		}

		if(cov[y]>=0)

		{

			if(cnt[cov[y]]==0) res--;

			cnt[cov[y]]++;

		}

		cov[y]--;

		a[x]=y;

		cout<<res<<'\n';

	}

}


// Faster C++ solution for the same problem (measured speedup: 5.1755995817056695x):
#include<cstdio>

#include<algorithm>

using namespace std;

#define MAXN 200010

int cnt[MAXN],a[MAXN],A[MAXN];

int n,m,x,y,ans;

int main()

{

	scanf("%d%d",&n,&m);

	for(int i=1;i<=n;i++)

	{

		scanf("%d",&A[i]);

		a[max(0,A[i]-cnt[A[i]])]++;

		cnt[A[i]]++;

	}

	for(int i=1;i<=n;i++)

		if(!a[i]) ans++;

	while(m--)

	{

		scanf("%d%d",&x,&y);

		int k=max(0,A[x]-cnt[A[x]]+1);

		if(k&&a[k]==1) ans++;

		a[k]--;

		cnt[A[x]]--;

		A[x]=y;

		k=max(0,A[x]-cnt[A[x]]);

		if(k&&a[k]==0) ans--;

		a[k]++;

		cnt[A[x]]++;

		printf("%d\n",ans);

	}

}
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;



typedef long long ll;

typedef pair<int, int> ii; 



const int N = 2e5 + 10; 

int n, m, a[N], cnt[N], p[N], tot;  



void add(int x) {

    int l = x - cnt[x]++; 

    if(l > 0 && ++p[l] == 1) 

        --tot; 

}

void rem(int x) {

    int l = x - --cnt[x]; 

    if(l > 0 && --p[l] == 0) 

        ++tot;

}



int main(int argc, char const *argv[]) {

    scanf("%d %d", &n, &m);

    for(int i = 1; i <= n; i++) {

        scanf("%d", &a[i]);

        add(a[i]); 

    } tot += n;  

    while(m--) {

        int x, y; 

        scanf("%d %d", &x, &y);

        rem(a[x]); a[x] = y; add(a[x]); 

        printf("%d\n", tot); 

    }

}


// Faster C++ solution for the same problem (measured speedup: 5.057888865419034x):
#include<cstdio>

#include<algorithm>

using namespace std;

#define MAXN 200010

int cnt[MAXN],a[MAXN],A[MAXN];

int n,m,x,y,ans;

int main()

{

	scanf("%d%d",&n,&m);

	for(int i=1;i<=n;i++)

	{

		scanf("%d",&A[i]);

		a[max(0,A[i]-cnt[A[i]])]++;

		cnt[A[i]]++;

	}

	for(int i=1;i<=n;i++)

		if(!a[i]) ans++;

	while(m--)

	{

		scanf("%d%d",&x,&y);

		int k=max(0,A[x]-cnt[A[x]]+1);

		if(k&&a[k]==1) ans++;

		a[k]--;

		cnt[A[x]]--;

		A[x]=y;

		k=max(0,A[x]-cnt[A[x]]);

		if(k&&a[k]==0) ans--;

		a[k]++;

		cnt[A[x]]++;

		printf("%d\n",ans);

	}

}
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;

typedef long long i64;



const int MAXN = 200000 + 10;



int N, M;

int A[MAXN];

int answer;



int covCnt[MAXN], ptr[MAXN];



void addSeg(int x)

{

	int newL = x - covCnt[x];

	covCnt[x] ++;

	if(newL > 0)

		ptr[newL]++;

	if(newL > 0 && ptr[newL] == 1)

		answer--;

}



void removeSeg(int x)

{

	covCnt[x]--;

	int newL = x - covCnt[x];

	

	if(newL > 0)

		ptr[newL]--;

	if(newL > 0 && ptr[newL] == 0)

		answer++;

}



int main()

{

	ios::sync_with_stdio(false), cin.tie(nullptr);



	cin >> N >> M;

	for(int i = 1; i <= N; i++)

		cin >> A[i], addSeg(A[i]);

	answer += N;



	for(int i = 1; i <= M; i++)

	{

		int x, y;

		cin >> x >> y ;

		removeSeg(A[x]);

		A[x] = y;

		addSeg(A[x]);

		cout << answer << endl ;

	}



	return 0;

}




// Faster C++ solution for the same problem (measured speedup: 5.178846270450866x):
#include<cstdio>

#include<algorithm>

using namespace std;

#define MAXN 200010

int cnt[MAXN],a[MAXN],A[MAXN];

int n,m,x,y,ans;

int main()

{

	scanf("%d%d",&n,&m);

	for(int i=1;i<=n;i++)

	{

		scanf("%d",&A[i]);

		a[max(0,A[i]-cnt[A[i]])]++;

		cnt[A[i]]++;

	}

	for(int i=1;i<=n;i++)

		if(!a[i]) ans++;

	while(m--)

	{

		scanf("%d%d",&x,&y);

		int k=max(0,A[x]-cnt[A[x]]+1);

		if(k&&a[k]==1) ans++;

		a[k]--;

		cnt[A[x]]--;

		A[x]=y;

		k=max(0,A[x]-cnt[A[x]]);

		if(k&&a[k]==0) ans--;

		a[k]++;

		cnt[A[x]]++;

		printf("%d\n",ans);

	}

}
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;



const int MAXN = 200005;

 

int n, m, ret, a[MAXN], b[MAXN], c[MAXN];

 

int main() {

  cin>>n>>m;

  ret = n;

	for (int i = 1; i <= n; i ++) {

    cin>>a[i];

    c[a[i]]++;

		if (a[i] - c[a[i]] >= 0 && ++b[a[i] - c[a[i]]] == 1)

			ret--;

	}

	while(m--) {

		int x, y; cin>>x>>y;

		if (a[x] - c[a[x]] >= 0 && !--b[a[x] - c[a[x]]])

			ret ++;

		c[a[x]]--;

		a[x] = y;

		c[a[x]] ++;

		if (a[x] - c[a[x]] >= 0 && ++b[a[x] - c[a[x]]] == 1)

			ret --;

		cout<<ret<<'\n';

	}

}

// Faster C++ solution for the same problem (measured speedup: 5.130427220346599x):
#include<cstdio>

#include<cstring>

#include<algorithm>

#define MAXN 200000

using namespace std;

int seq[MAXN+5],cnt[MAXN+5],N,M;

int A[MAXN+5];

int main()

{

	scanf("%d %d",&N,&M);

	for(int i=1;i<=N;i++)

		scanf("%d",&seq[i]),cnt[seq[i]]++;

	for(int i=1;i<=N;i++)

		for(int j=max(1,i-cnt[i]+1);j<=i;j++)

			A[j]++;

	int ans=0;

	for(int i=1;i<=N;i++)

		if(A[i]==0)

			ans++;

	int X,Y;

	for(int i=1;i<=M;i++)

	{

		scanf("%d %d",&X,&Y);

		if(seq[X]-cnt[seq[X]]+1>=1)

		{

			A[seq[X]-cnt[seq[X]]+1]--;

			if(A[seq[X]-cnt[seq[X]]+1]==0)

				ans++;

		}

		cnt[seq[X]]--;

		seq[X]=Y;

		cnt[seq[X]]++;

		if(seq[X]-cnt[seq[X]]+1>=1)

		{

			if(A[seq[X]-cnt[seq[X]]+1]==0)

				ans--;

			A[seq[X]-cnt[seq[X]]+1]++;

		}

		printf("%d\n",ans);

	}

	return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>

#include <climits>

#define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))

#define srep(i, begin, end) for (__typeof(end) i = begin; i != end; i++)

#define si(x) int x = scanInt();

#define sll(x) LL x = scanLong();

#define sci(x) int x; scanf("%d", &x);

#define scll(x) LL x; scanf("%lld", &x);

#define pi(x) printf("%d ", x)

#define pll(x) printf("%lld ", x)

#define ps(x) printf("%s", x)

#define nl printf("\n")

#define clr(a) memset(a, 0, sizeof(a))

#define PB push_back

#define MP make_pair

using namespace std;

typedef unsigned int UI; // 32 bit integer

typedef long int LI; // 32 bit integer

typedef unsigned long int ULI; // 32 bit unsigned integer

typedef long long int LL; // 64 bit integer

typedef unsigned long long int  ULL; // 64 bit unsigned integer

typedef long double LD;

typedef vector<int> VI;

typedef vector<LL> VLL;

typedef pair<int, int> PII;

typedef pair<LL, LL> PLL;

LL mod = 1e9+7;



/* Fast I/O */

inline int scanInt() {

	int n = 0;

	char ch = getchar();

	int sign = 1;

	while(ch < '0' || ch > '9') {

		if(ch == '-')	sign = -1;

		ch = getchar();

	}

	while(ch >= '0' && ch <= '9') {

		n = (n<<1)+(n<<3)+(int)(ch-'0');

		ch = getchar();

	}

	return n*sign;

}



inline LL scanLong() {

	LL n = 0;

	char ch = getchar();

	LL sign = 1;

	while(ch < '0' || ch > '9') {

		if(ch == '-')	sign = -1;

		ch = getchar();

	}

	while(ch >= '0' && ch <= '9') {

		n = (n<<1)+(n<<3)+(LL)(ch-'0');

		ch = getchar();

	}

	return n*sign;

}



const LL MAXN = 2e5+10;	

LL arr[MAXN], cnt[MAXN], present[MAXN];



int main() {

	sll(n); sll(m);

	rep(i, 0, n) {

		arr[i] = scanLong();

		cnt[arr[i]]++;

	}

	rep(i, 1, n+1) {

		LL low = max(0ll, i - cnt[i]);

		rep(j, low, i)	present[j]++;

	}

	LL ans = 0;

	rep(i, 0, n)	if(!present[i])	ans++;

	rep(i, 0, m) {

		sll(x); sll(y); x--;

		if(y != arr[x]) {

			if(y > cnt[y]) {

				if(present[y-cnt[y]-1] == 0)	ans--;

				present[y-cnt[y]-1]++;

			}

			if(arr[x] >= cnt[arr[x]]) {

				if(present[arr[x]-cnt[arr[x]]] == 1)	ans++;

				present[arr[x]-cnt[arr[x]]]--;

			}

			cnt[arr[x]]--;

			cnt[y]++;

			arr[x] = y;

		}

		pll(ans); nl;

	}

}


// Faster C++ solution for the same problem (measured speedup: 5.0341306696754105x):
#include<cstdio>

#include<cstring>

#include<algorithm>

#define MAXN 200000

using namespace std;

int seq[MAXN+5],cnt[MAXN+5],N,M;

int A[MAXN+5];

int main()

{

	scanf("%d %d",&N,&M);

	for(int i=1;i<=N;i++)

		scanf("%d",&seq[i]),cnt[seq[i]]++;

	for(int i=1;i<=N;i++)

		for(int j=max(1,i-cnt[i]+1);j<=i;j++)

			A[j]++;

	int ans=0;

	for(int i=1;i<=N;i++)

		if(A[i]==0)

			ans++;

	int X,Y;

	for(int i=1;i<=M;i++)

	{

		scanf("%d %d",&X,&Y);

		if(seq[X]-cnt[seq[X]]+1>=1)

		{

			A[seq[X]-cnt[seq[X]]+1]--;

			if(A[seq[X]-cnt[seq[X]]+1]==0)

				ans++;

		}

		cnt[seq[X]]--;

		seq[X]=Y;

		cnt[seq[X]]++;

		if(seq[X]-cnt[seq[X]]+1>=1)

		{

			if(A[seq[X]-cnt[seq[X]]+1]==0)

				ans--;

			A[seq[X]-cnt[seq[X]]+1]++;

		}

		printf("%d\n",ans);

	}

	return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>

#define R register

namespace IO{

	char buf[1<<15],*S,*T;

	inline char gc(){

		if (S==T){

			T=(S=buf)+fread(buf,1,1<<15,stdin);

			if (S==T) return EOF;

		}return *S++;

	}

	inline int read(){

		R int x; R bool f; R char c;

		for (f=0; (c=gc())<'0'||c>'9'; f=c=='-');

		for (x=c^'0'; (c=gc())>='0'&&c<='9'; x=(x<<1)+(x<<3)+(c^'0'));

		return f?-x:x;

	}

	const int outlim=1<<20;int cnt=0;

	char outbuf[outlim+5],*SS=outbuf;

	inline void pc(char c){

		*SS++=c;++cnt;if (cnt==outlim)

			fwrite(outbuf,1,outlim,stdout),SS=outbuf,cnt=0;

	}

	inline void write(int x){

		if (x>9) write(x/10);

		pc(x%10^'0');

	}

	void endfile(){

		if (cnt)

			fwrite(outbuf,1,cnt,stdout);

		fclose(stdin);fclose(stdout);

	}

}

#define MN 200005

#define M (1<<18)

int vl[MN],cnt[MN],n,m,T[M<<1];

inline void rw(int k,int x){

	if (k<1) return;

	if (!T[k+=M]) for (; k; k>>=1) ++T[k];

	else{

		if (~x) ++T[k];

		else if (!(--T[k])) for (; k>>=1; ) --T[k];

	}

}

int main(){

	n=IO::read(),m=IO::read();

	for (R int i=1; i<=n; ++i) ++cnt[vl[i]=IO::read()],rw(vl[i]-cnt[vl[i]]+1,1);

	for (R int i=1,x,y; i<=m; ++i){

		x=IO::read(),y=IO::read();

		--cnt[vl[x]];rw(vl[x]-cnt[vl[x]],-1);

		vl[x]=y;rw(y-cnt[y],1);++cnt[y];

		IO::write(n-T[1]);IO::pc('\n');

	}IO::endfile();return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.030831296300954x):
#include<cstdio>

#include<cstring>

#include<algorithm>

#define MAXN 200000

using namespace std;

int seq[MAXN+5],cnt[MAXN+5],N,M;

int A[MAXN+5];

int main()

{

	scanf("%d %d",&N,&M);

	for(int i=1;i<=N;i++)

		scanf("%d",&seq[i]),cnt[seq[i]]++;

	for(int i=1;i<=N;i++)

		for(int j=max(1,i-cnt[i]+1);j<=i;j++)

			A[j]++;

	int ans=0;

	for(int i=1;i<=N;i++)

		if(A[i]==0)

			ans++;

	int X,Y;

	for(int i=1;i<=M;i++)

	{

		scanf("%d %d",&X,&Y);

		if(seq[X]-cnt[seq[X]]+1>=1)

		{

			A[seq[X]-cnt[seq[X]]+1]--;

			if(A[seq[X]-cnt[seq[X]]+1]==0)

				ans++;

		}

		cnt[seq[X]]--;

		seq[X]=Y;

		cnt[seq[X]]++;

		if(seq[X]-cnt[seq[X]]+1>=1)

		{

			if(A[seq[X]-cnt[seq[X]]+1]==0)

				ans--;

			A[seq[X]-cnt[seq[X]]+1]++;

		}

		printf("%d\n",ans);

	}

	return 0;

}
// Slower C++ solution:
#include <iostream>

#include <vector>

#include <cstdio>

#include <algorithm>

#include <utility>

#include <string>

#include <cmath>

#include <set>

#include <functional>

#include <map>

#include <queue>

#include <cstring>

#include <stack>

#include <iomanip>

#include <climits>

#include <numeric>

#include <cassert>

#include <cstring>

using namespace std;

#define rep(i,n) for(int i = 0; i < (n); ++i)

#define show(x) cout << #x << " = " << x << endl;

typedef long long ll;

typedef pair<int,int> pii;

int main(){

    int n,m;

    cin.tie(0);

    ios::sync_with_stdio(false);

    cin >> n >> m;

    vector<int>a(n);

    vector<int>x(m),y(m);

    vector<int>c(n+1,0);

    rep(i,n){

        cin >> a[i];

        c[a[i]]++;

    }

    int ans = 0;

    map<int,int>k;

    for(int i = 1; i <= n; i++){

        for(int j = i-1; j >= i-c[i] ; j--){

            k[j]++;

        }

    }

    for(int i = 0; i < n; i++){

        if(k[i] == 0){

            ans++;

        }

    }

    rep(i,m){

        cin >> x[i] >> y[i];

        x[i]--;

        int old = a[x[i]];

        int now = y[i];

        if(old == now){

            cout << ans << endl;

            continue;

        }

        k[now-c[now]-1]++;

        if(k[now-c[now]-1]==1 && now-c[now]-1>=0)ans--;

        k[old-c[old]]--;

        if(k[old-c[old]]==0 && old-c[old] >= 0)ans++;

        cout <<ans << endl;

        c[a[x[i]]]--;

        c[y[i]]++;

        a[x[i]] = y[i];

    }

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.106720255461773x):
#include <vector>

#include <cstdio>

#include <algorithm>

#include <utility>

#include <string>

#include <cmath>

#include <set>

#include <functional>

#include <map>

#include <queue>

#include <cstring>

#include <stack>

#include <iomanip>

#include <climits>

#include <numeric>

#include <cassert>

#include <cstring>

using namespace std;

#define rep(i,n) for(int i = 0; i < (n); ++i)

#define show(x) cout << #x << " = " << x << endl;

typedef long long ll;

typedef pair<int,int> pii;

int main(){

    int n,m;

    scanf("%d %d",&n,&m);

    vector<int>a(n);

    vector<int>x(m),y(m);

    vector<int>c(n+1,0);

    rep(i,n){

        scanf("%d",&a[i]);

        c[a[i]]++;

    }

    int ans = 0;

    vector<int>k(n*2,0);

    for(int i = 1; i <= n; i++){

        for(int j = i-1+n; j >= i-c[i]+n ; j--){

            k[j]++;

        }

    }

    for(int i = n; i < n*2; i++){

        if(k[i] == 0){

            ans++;

        }

    }

    rep(i,m){

        scanf("%d %d", &x[i], &y[i]);

        x[i]--;

        int old = a[x[i]];

        int now = y[i];

        if(old == now){

            printf("%d\n", ans);

            continue;

        }

        k[n+now-c[now]-1]++;

        if(k[n+now-c[now]-1]==1 && now-c[now]-1>=0)ans--;

        k[n+old-c[old]]--;

        if(k[n+old-c[old]]==0 && old-c[old] >= 0)ans++;

        printf("%d\n", ans);

        c[a[x[i]]]--;

        c[y[i]]++;

        a[x[i]] = y[i];

    }

    return 0;

}
// Slower C++ solution:
#include<iostream>

#include<cstdio>

using namespace std;

int n,m,a[200005],b[200005],cnt[200005],x,y,ans;

inline int read(){

	char c=getchar();

	for(;c>'9'||c<'0';) c=getchar();

	int xx=c-'0';

	c=getchar();

	for(;c>='0'&&c<='9';){

		xx=(xx<<3)+(xx<<1)+c-'0';

		c=getchar();

	}

	return xx;

}

int main(){

	n=read(),m=read(),ans=n;

	for(int i=1;i<=n;i++){

		cnt[a[i]=read()]++;

		if(a[i]-cnt[a[i]]>=0){

			if(!b[a[i]-cnt[a[i]]]) ans--;

			b[a[i]-cnt[a[i]]]++;

		}

	}

	for(int i=1;i<=m;i++){

		x=read(),y=read();

		if(a[x]-cnt[a[x]]>=0){

			b[a[x]-cnt[a[x]]]--;

			if(!b[a[x]-cnt[a[x]]]) ans++;

		}

		cnt[a[x]]--,a[x]=y,cnt[y]++;

		if(a[x]-cnt[a[x]]>=0){

			b[a[x]-cnt[a[x]]]++;

			if(b[a[x]-cnt[a[x]]]==1) ans--;

		}

		printf("%d\n",ans);

	}

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.170580853184033x):
#include <cstdio>

#include <algorithm>

#include <cstring>

#define MN 200005

using namespace std;

int mp[MN],a[MN],sm[MN];

int tot,n,m;



inline int read()

{

	int n=0,f=1; char c=getchar();

	while (c<'0' || c>'9') {if(c=='-')f=-1; c=getchar();}

	while (c>='0' && c<='9') {n=n*10+c-'0'; c=getchar();}

	return n*f;

}



int main()

{

	register int i,j,x,y;

	n=read(); m=read();

	for (i=1;i<=n;++i) ++mp[a[i]=read()];

	for (i=1;i<=n;++i)

		for (j=0;j<i&&j<mp[i];++j)

			if (sm[i-j]++==0) ++tot;

	while (m--)

	{

		x=read(); y=read();

		--mp[a[x]];

		if (mp[a[x]]<a[x])

			if (--sm[a[x]-mp[a[x]]]==0) --tot;

		if (mp[y]<y)

			if (sm[y-mp[y]]++==0) ++tot;

		++mp[y]; a[x]=y;

		printf("%d\n",n-tot);

	}

}
// Slower C++ solution:
#include<iostream>

#include<cstdio>

using namespace std;

int n,m,a[200005],b[200005],cnt[200005],x,y,ans;

inline int read(){

	char c=getchar();

	for(;c>'9'||c<'0';) c=getchar();

	int xx=c-'0';

	c=getchar();

	for(;c>='0'&&c<='9';){

		xx=(xx<<3)+(xx<<1)+c-'0';

		c=getchar();

	}

	return xx;

}

int main(){

	n=read(),m=read(),ans=n;

	for(int i=1;i<=n;i++){

		cnt[a[i]=read()]++;

		if(a[i]-cnt[a[i]]>=0){

			if(!b[a[i]-cnt[a[i]]]) ans--;

			b[a[i]-cnt[a[i]]]++;

		}

	}

	for(int i=1;i<=m;i++){

		x=read(),y=read();

		if(a[x]-cnt[a[x]]>=0){

			b[a[x]-cnt[a[x]]]--;

			if(!b[a[x]-cnt[a[x]]]) ans++;

		}

		cnt[a[x]]--,a[x]=y,cnt[y]++;

		if(a[x]-cnt[a[x]]>=0){

			b[a[x]-cnt[a[x]]]++;

			if(b[a[x]-cnt[a[x]]]==1) ans--;

		}

		printf("%d\n",ans);

	}

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 4.984036657060702x):
#include<cstdio>

#include<algorithm>

#define maxn 200005

using namespace std;

int n,m,a[maxn],cnt[maxn],ccnt[maxn*2],l;

int Query(int x)

{

	int res=0;

	for(;x;x-=x&(-x)) res+=ccnt[x];

	return res;

}

void Modify(int x,int d)

{

	for(;x<=n*2;x+=x&(-x)) ccnt[x]+=d;

}

int main()

{

	scanf("%d%d",&n,&m);

	for(int i=1;i<=n;i++) 

	{

		scanf("%d",&a[i]);

		cnt[a[i]]++;

	}

	for(int i=1;i<=n;i++) { Modify(i-cnt[i]+n+1,1); Modify(i+n+1,-1); }

	for(int i=n+1;i<=n*2;i++)

		if(!Query(i)) l++;

	while(m--)

	{

		int x,y;

		scanf("%d%d",&x,&y);

		cnt[a[x]]--;

		Modify(a[x]-cnt[a[x]]+n,-1); Modify(a[x]-cnt[a[x]]+n+1,1);

		if(!Query(max(a[x]-cnt[a[x]]+n,n+1))) l++;

		//printf(" * %d %d\n",max(a[x]-cnt[a[x]]+n,n+1),Query(max(a[x]-cnt[a[x]]+n,n+1)));

		a[x]=y;

		Modify(a[x]-cnt[a[x]]+n,1); Modify(a[x]-cnt[a[x]]+n+1,-1);

		if(a[x]-cnt[a[x]]>0&&Query(a[x]-cnt[a[x]]+n)==1) l--;

		cnt[a[x]]++;

		//for(int i=n+1;i<=n*2;i++)

		//	printf(" - %d %d\n",i-n,Query(i));

		printf("%d\n",l);

	}

}
// Slower C++ solution:
#include <iostream>



using namespace std;



int main()

{

    int x;

    cin >> x;



    if (x < 1200){

        cout << "ABC" << endl;

    }else{

        cout << "ARC" << endl;

    }

}


// Faster C++ solution for the same problem (measured speedup: 5.3162108516029605x):
#include<stdio.h>

int main()

{

	int input;

	scanf("%d",&input);

	if(input<1200){

		printf("ABC\n");

	}

	else{

		printf("ARC\n");

	}

	return 0;

}