#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pir pair<ll,ll>
#define ls first
#define rs second
#define mp make_pair
#define mod
#define MAXN 200010
#define len 550
#define qmod(x) (x>mod?x-mod:x)
#define V 200000
#define debug cout << "flyfreemrn\n";
inline ll read(){
    ll x = 0,f = 1;
    char c = getchar();
    while(c < '0'||c > '9'){
        if(c == '-')f = -1;
        c = getchar();
    }
    while(c >= '0'&&c <= '9'){
        x = x*10+c-'0';
        c = getchar();
    }
    return x*f;
}
ll n,q,maxz;
ll cnt[MAXN];
vector <ll> vec;
set <ll> st[MAXN];
ll suf_min[MAXN],suf_max[MAXN];
ll a[MAXN];
ll pos[MAXN],to[MAXN];

void update(ll pos){
    suf_max[pos] = suf_max[pos + 1];
    suf_min[pos] = suf_min[pos + 1]; 
    if(st[pos].end() == st[pos].begin())return;
    suf_max[pos] = max(suf_max[pos + 1], *(-- st[pos].end()));
    suf_min[pos] = min(suf_min[pos + 1], *(st[pos].begin()));
}

void insert(ll val){
    st[cnt[val]].erase(val);
    if(maxz == cnt[val])maxz = cnt[val] + 1;
    ++ cnt[val];
    st[cnt[val]].insert(val);
    update(cnt[val]);
    update(cnt[val] - 1);
}

void del(ll val){
    st[cnt[val]].erase(val);
    if(maxz == cnt[val] && st[cnt[val]].begin() == st[cnt[val]].end())maxz = cnt[val] - 1;
    -- cnt[val];
    st[cnt[val]].insert(val);
    update(cnt[val] + 1);
    update(cnt[val]);
}


int main(){
    freopen("Queries.in", "r", stdin);
    freopen("Queries.out", "w", stdout);
    n = read(),q = read();
    for(int i = 1;i <= n; ++i){
        a[i] = read();
        ++ cnt[a[i]];
    }
    for(int i = 1;i <= q; ++i){
        pos[i] = read(),to[i] = read();
        ++ cnt[to[i]];
    }
    for(int i = 1;i <= n; ++i){
        if(cnt[i] >= len)vec.push_back(i);
        cnt[i] = 0;
    }
    for(int i = 1;i <= n; ++i){
        ++ cnt[a[i]];
    }
    for(int i = 1;i <= n; ++i){
        maxz = max(maxz, cnt[a[i]]);
        st[cnt[a[i]]].insert(a[i]);
    }
    suf_min[V + 1] = 1e18;
    suf_max[V + 1] = 0;
    for(int i = V;i; --i){
        update(i);
    }
    for(int i = 1;i <= q; ++i){
        del(a[pos[i]]);
        insert(to[i]);
        a[pos[i]] = to[i];
        ll ans = 0;
        // debug;
        for(int j = 0;j < vec.size(); ++j){
            ll qs_min = suf_min[max(maxz - cnt[vec[j]], 1ll)];
            ll qs_max = suf_max[max(maxz - cnt[vec[j]], 1ll)];
            ans = max(ans, abs(vec[j] - qs_min));
            ans = max(ans, abs(vec[j] - qs_max));
        }
        for(int j = 1;j < len; ++j){
            // cout << j << endl;
            if(st[j].begin() == st[j].end())continue;
            ll now_min = *st[j].begin();
            ll now_max = *(-- st[j].end());
            ll qs_min = suf_min[max(maxz - j, 1ll)];
            ll qs_max = suf_max[max(maxz - j, 1ll)];
            ans = max(ans, abs(now_max - qs_min));
            ans = max(ans, abs(now_min - qs_max));
        }
        cout << ans << endl;
    }
    return 0;
}