#define _CRT_SECURE_NO_WARNINGS
#define debug(tl) cerr<<#tl<<' '<<tl<<'\n';
#include "bits/stdc++.h"
using namespace std;
#define all(d) d.begin(), d.end()
signed main() {
#ifdef _DEBUG
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n, q;
    cin >> n >> q;
    vector<int> cnt(2e5 + 44);
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        a[i] = x;
        cnt[x]++;
    }
    set<int> mx;
    for (int i = 2; i <= 2e5 + 43; i++) {
        cnt[i] += (cnt[i - 1] / 2);
        if(cnt[i])mx.insert(i);
    }
    for (int i = 0; i < q; i++) {
        int k, l;
        cin >> k >> l;
        k--;
        for (int j = a[k]; j <= 2e5; j++) {
            if (cnt[j] % 2 == 0) {
                cnt[j]--;
                continue;
            }
            else {
                cnt[j]--;
                if (!cnt[j]) {
                    mx.erase(j);
                }
                break;
            }
        }
        a[k] = l;
        for (int j = a[k]; l <= 2e5 + 43; j++) {
            if (cnt[j] & 1) {
                cnt[j]++;
                continue;
            }
            else {
                cnt[j]++;
                if (cnt[j] == 1) {
                    mx.insert(j);
                }
                break;
            }
        }
        cout << *--mx.end() << '\n';
    }
    /*int n;
    cin >> n;
    string s(n, 'F');
    int sum;
    auto ask = [&](int& x) {
        cout << s << endl;
        cin >> x;
    };
    ask(sum);
    for (int i = 0; i < n; i++) {
        if (i + 1 < n) {
            s[i] = 'T', s[i + 1] = 'T';
            int ne;
            ask(ne);
            if (ne + 2 == sum) {
                s[i] = 'F', s[i + 1] = 'F';
                sum = ne;
                continue;
            }
            else if(ne == sum){

            }
            else {
                continue;
            }
        }
        else {

        }
    }*/
}