#include <bits/stdc++.h>
#define ll long long
#define rll register ll
#define cll const ll
#define N 200005
using namespace std;
inline ll read()
{
    rll x=0;bool f=1;register char c=getchar();
    while(c<48||c>57){if(c=='-') f=0;c=getchar();}
    while(c>=48&&c<=57){x=x*10+(c^48);c=getchar();}
    return f?x:-x;
}
inline void write(ll x)
{
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+48);
}
cll n=read();
ll q=read(),ans,a[N];
map<ll,ll> cnt;
set<ll> s;
set<ll>::iterator it,it2;
inline ll work(ll x)
{
    it=s.lower_bound(x);
    if(it==s.begin()) return -1;
    it2=it,it2--;
    if(*it-*it2>1) return *it2+1;
}
int main()
{
    for(rll i=1;i<=n;i++)
        a[i]=read(),s.insert(a[i]),cnt[a[i]]++;
    s.insert(1e18);
    for(it=s.begin();it!=s.end();it++)
    {
        if(it==s.begin()) continue;
        it2=it,it2--;
        if(*it-*it2>1)
        {
            ans=*it2+1;
            break;
        }
    }
    //write(ans),putchar('\n');
    while(q--)
    {
        rll x=read(),k=read(),t;
        cnt[a[x]]--,s.erase(a[x]);
        if(cnt[a[x]]) s.insert(a[x]);
        t=work(a[x]);
        if(~t) ans=t;
        //cout << "t=" << t << ' ';
        it=s.lower_bound(a[x]);
        s.insert(k),a[x]=k,cnt[k]++;
        //cout << "set:";
        //for(it=s.begin();it!=s.end();it++)
        //    cout << *it << ' ';
        //cout << '\n';
        t=work(k);
        //cout << "t=" << t << '\n';
        if(~t) ans=min(ans,t);
        t=work(1e18);
        if(~t) ans=min(ans,t);
        write(ans),putchar('\n');
    }
    return 0;
}