#include<bits/stdc++.h>
#define endl '\n'
#define int long long
#define double long double
using namespace std;
constexpr int N=1e7+10;
constexpr int mod=1e16+10;
void solve()
{
    int n,k;
    cin >> n >> k;
    vector<int> f(n+1);
    map<int,int> mp;
    for(int i=1;i<=n;i++)
    {
        cin >> f[i];
        mp[f[i]]++;
    }
    int cnt=0;
    for(auto [v,w]:mp)
    {
        if(v==cnt&&w)
            cnt++;
        else break;
    }
    while(k--)
    {
        int num,tmp;
        cin >> num >> tmp;
        int res=f[num];
        mp[f[num]]--;
        f[num]=tmp;
        mp[tmp]++;
        if(mp[cnt]&&mp[res]==0)
        {
            cnt=res;
        }else if(mp[cnt]==0&&mp[res])
        {
            cnt=cnt;
        }else if(mp[cnt]==0&&mp[res]==0)
        {
            cnt=min(cnt,res);
        }else
        {
            for(int i=max(cnt,res);;i++)
            {
                if(mp[i]==0)
                {
                    cnt=i;
                    break;
                }
            }
        }
        cout << cnt << endl;
    }
}
signed main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    // int o;
    // cin >> o;
    // while(o--)
    solve();
    return 0;
}
//
//⠀⠀⠀             ⠀⢸⣿⣿⣿⠀⣼⣿⣿⣦⡀
//⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⠀⠀⠀ ⠀⢸⣿⣿⡟⢰⣿⣿⣿⠟⠁
//⠀⠀⠀⠀⠀⠀⠀⢰⣿⠿⢿⣦⣀⠀⠘⠛⠛⠃⠸⠿⠟⣫⣴⣶⣾⡆
//⠀⠀⠀⠀⠀⠀⠀⠸⣿⡀⠀⠉⢿⣦⡀⠀⠀⠀⠀⠀⠀ ⠛⠿⠿⣿⠃
//⠀⠀⠀⠀⠀⠀⠀⠀⠙⢿⣦⠀⠀⠹⣿⣶⡾⠛⠛⢷⣦⣄⠀
//⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣿⣧⠀⠀⠈⠉⣀⡀⠀ ⠀⠙⢿⡇
//⠀⠀⠀⠀⠀⠀⢀⣠⣴⡿⠟⠋⠀⠀⢠⣾⠟⠃⠀⠀⠀⢸⣿⡆
//⠀⠀⠀⢀⣠⣶⡿⠛⠉⠀⠀⠀⠀⠀⣾⡇⠀⠀⠀⠀⠀⢸⣿⠇
//⢀⣠⣾⠿⠛⠁⠀⠀⠀⠀⠀⠀⠀⢀⣼⣧⣀⠀⠀⠀⢀⣼⠇
//⠈⠋⠁⠀⠀⠀⠀⠀⠀⠀⠀⢀⣴⡿⠋⠙⠛⠛⠛⠛⠛⠁
//⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣾⡿⠋⠀
//⠀⠀⠀⠀⠀⠀⠀⠀⢾⠿⠋⠀
//