#include <bits/stdc++.h>
#define all(a) a.begin(), a.end()
#define int long long
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

void solve(){
    int n, q;
    cin >> n >> q;
    vector<int> a(n+1);
    vector<pii> d;

    for(int i = 1; i <= n; i++){
        cin >> a[i];
        d.emplace_back(a[i], i);
    }
    vector<pair<int, int> > upd(q);
    for(auto& [x, v] : upd){
        cin >> x >> v;
        d.emplace_back(v, x);
    }
    d.emplace_back(0, 0);
    sort(all(d));
    d.erase(unique(all(d)), d.end());

    auto find = [&](pii x)->int{
        return lower_bound(all(d), x) - d.begin() + 1;
    };

    vector<int> sBIT(d.size() + 1);
    vector<int> cBIT(d.size() + 1);

    auto add = [&](vector<int>& BIT, int x, int val)->void{
        for(int i = x; i <= d.size(); i += i&-i) BIT[i] += val;
    };

    auto qry = [&](vector<int>& BIT, int x){
        int res = 0;
        for(int i = x; i > 0; i -= i&-i) res += BIT[i];
        return res;
    };

    for(int i = 1; i <= n; i++){
        add(sBIT, find({a[i], i}), a[i]);
        add(cBIT, find({a[i], i}), 1);
    }

    auto f = [&](int x)->bool{
        int neg = qry(sBIT, find({0, 0}));
        int xthpos = qry(sBIT, x);
        int rmpos = qry(sBIT, d.size()) - xthpos;
        xthpos -= neg;

        return rmpos >= rmpos + neg + xthpos;
    };

    for(auto [x, v] : upd){
        add(sBIT, find({a[x], x}), -a[x]);
        add(cBIT, find({a[x], x}), -1);
        a[x] = v;
        add(sBIT, find({a[x], x}), a[x]);
        add(cBIT, find({a[x], x}), 1);

        int i = find({0, 0});
        for(int j = d.size(); j > 0; j /= 2){
            while(i+j <= d.size() && f(i+j)) i += j;
        }

        int min_k = qry(cBIT, d.size()) - qry(cBIT, i);
        int max_k = qry(cBIT, d.size()) - qry(cBIT, find({0, 0}));
        
        cout << max_k - min_k + 1 << '\n'; 
    }
}

int32_t main(){
    ios::sync_with_stdio(false);
    cin.tie(0);

    int tt = 1;
    // cin >> tt;
    while(tt--){
        solve();
    }
}