#include <iostream>
#include <vector>
#include <set>
#include <map>

using namespace std;

typedef long long ll;

map<ll, int> freq;
set<ll> vals;
multiset<ll> gaps;

void add_val(ll x) {
    if (++freq[x] == 1) {
        auto it = vals.insert(x).first;
        auto nxt = next(it);
        auto prv = (it == vals.begin() ? vals.end() : prev(it));
        
        if (prv != vals.end() && nxt != vals.end()) {
            gaps.erase(gaps.find(*nxt - *prv));
        }
        if (prv != vals.end()) gaps.insert(x - *prv);
        if (nxt != vals.end()) gaps.insert(*nxt - x);
    }
}

void rem_val(ll x) {
    if (--freq[x] == 0) {
        auto it = vals.find(x);
        auto nxt = next(it);
        auto prv = (it == vals.begin() ? vals.end() : prev(it));
        
        if (prv != vals.end()) gaps.erase(gaps.find(x - *prv));
        if (nxt != vals.end()) gaps.erase(gaps.find(*nxt - x));
        if (prv != vals.end() && nxt != vals.end()) {
            gaps.insert(*nxt - *prv);
        }
        vals.erase(it);
    }
}

ll get_ans() {
    if (vals.empty()) return 0;
    ll max_val = *vals.rbegin();
    ll max_gap = (gaps.empty() ? 0 : *gaps.rbegin());
    return max_val + max_gap;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(NULL);
    
    int n, q;
    cin >> n >> q;
    vector<ll> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        add_val(a[i]);
    }
    
    while (q--) {
        int idx; ll val;
        cin >> idx >> val;
        idx--; // Chuyển về 0-indexed nếu cần
        rem_val(a[idx]);
        a[idx] = val;
        add_val(a[idx]);
        cout << get_ans() << "\n";
    }
    
    return 0;
}