An important property of \(\rm{mex}\) is that the \(\rm{mex}\) of a length-\(N\) sequence of non-negative integers is between \(0\) and \(N\), inclusive.A
Proof: the sequence has \(N\) integers, but there are \((N+1)\) integers between \(0\) and \(N\). Thus, at least one of them is not contained in the sequence.

Therefore, we can ignore any element greater than \(N\) in the sequence \(N\). (We can “regard all such elements \(N+1\)” or “skip the operation,” for example.)

While processing the queries, let us maintain \(\rm{bk}\)\([i] = \) (the number of \(i\) in \(A\)). What we want is the minimum \(k\) such that \(\rm{bk}\)\([k]=0\).

This can be discovered by the following procedure.

• First, prepare a data structure \(s\) that supports “addition of an integer,” “removal of a specified integer,” and “retrieval of the minimum value.” (You can use the set in C++ or exploit max_right of segtree in ACL (AtCoder Library).)
• Next, compute the initial value of \(\rm{bk}\).
  • Here, find all the \(k\) such that \(\rm{bk}\)\([k]=0\) and put them into \(s\).
• Process each query as follows.
  • First, for \(A_{i_k}\) before the update, decrement \(\rm{bk}\)\([A_{i_K}]\).
    • Here, if \(\rm{bk}\)\([A_{i_K}]\) becomes \(0\), insert \(A_{i_K}\) to \(s\).
  • Set \(A_{i_k}\) to \(x_k\).
  • For \(A_{i_k}\) after the update, increment \(\rm{bk}\)\([A_{i_K}]\).
    • Here, if \(\rm{bk}\)\([A_{i_K}]\) used to be \(0\), remove \(A_{i_K}\) from \(s\).
  • The minimum value of \(s\) at this point is the answer up to this query.

Sample code 1 (C++):

#include<bits/stdc++.h>

using namespace std;

int main(){
  int n,q;
  cin >> n >> q;
  vector<int> bk(n+1,0);
  vector<int> a(n);
  for(int i=0;i<n;i++){
    cin >> a[i];
    if(a[i]<=n){
      bk[a[i]]++;
    }
  }
  set<int> st;
  for(int i=0;i<=n;i++){
    if(bk[i]==0){st.insert(i);}
  }
  while(q>0){
    q--;
    int i,x;
    cin >> i >> x;
    i--;
    if(a[i]<=n){
      bk[a[i]]--;
      if(bk[a[i]]==0){st.insert(a[i]);}
    }
    a[i]=x;
    if(a[i]<=n){
      if(bk[a[i]]==0){st.erase(a[i]);}
      bk[a[i]]++;
    }
    cout << (*st.begin()) << "\n";
  }
  return 0;
}

Sample code 2 (C++):

#include<bits/stdc++.h>
#include<atcoder/segtree>

using namespace std;
using namespace atcoder;

int op(int a,int b){return min(a,b);}
int e(){return 1e9;}
bool f(int x){return (x>0);}

int main(){
  int n,q;
  cin >> n >> q;
  vector<int> bk(n+1,0);
  vector<int> a(n);
  for(int i=0;i<n;i++){
    cin >> a[i];
    if(a[i]<=n){bk[a[i]]++;}
  }
  segtree<int,op,e> seg(bk);
  for(int i=0;i<q;i++){
    int p,x;
    cin >> p >> x;
    p--;
    if(a[p]<=n){
      seg.set(a[p],seg.get(a[p])-1);
    }
    a[p]=x;
    if(a[p]<=n){
      seg.set(a[p],seg.get(a[p])+1);
    }
    cout << seg.max_right<f>(0) << "\n";
  }
  return 0;
}