#include <bits/stdc++.h>
#define int long long 
const int inf = 1e9;
using namespace std;
#define For(i,a,b) for(int i = a; i <= b; ++i)
class sgt{
    public:
        int n,num,root ;
        vector<int> cnt,sum,ls,rs;
        sgt(int _n){
            n = _n;
            num = 1;
            root = 1;
            sum.resize(n * 35);
            cnt.resize(n * 35);
            ls.resize(n * 35);
            rs.resize(n * 35);
        }
        #define mid ((l + r ) >> 1ll)
        void update(int &pos,int l,int r,int x,int v,int flag){
            if(!pos) pos = ++num;
            cnt[pos] += flag;
            sum[pos] += v * flag;
            if(l == r)  return;
            if(x <= mid)
                update(ls[pos],l,mid,x,v,flag);
            else    
                update(rs[pos],mid + 1,r,x,v,flag);
        }
        pair<int,int> query(int pos,int l,int r,int cur){
            // if(!sum[pos])
            if(!pos)
             return make_pair(0,0);
            if(l == r){
                if(cur + sum[pos] > 0){
                    return make_pair(sum[pos] / l,1);
                }
                else
                    return make_pair(0,0);
            }
            pair<int,int> ansl, ansr ;
            ansl = ansr = make_pair(0,0);
            ansl = query(ls[pos],l,mid,cur);
            if(ansl.second == 1){
                return ansl;
            }
            ansr = query(rs[pos],mid + 1,r,cur + sum[ls[pos]]);
            if(ansr.second == 1){
                ansr.first += cnt[ls[pos]];
                return ansr;
            }
            return make_pair(0,0);
        }
        void del(int v){
            update(root,-inf,inf,v,v,-1);
        }
        void add(int v){
            update(root,-inf,inf,v,v,1);
        }
        int Q(){
            return query(root,-inf,inf,0).first;
        }
};
signed main()
{
    #ifdef NICEGUODONG
        freopen("data.in","r",stdin);
    #endif
    int n,q;
    cin >> n >> q;
    vector<int> a(n  + 1);
    int maxx = 0;
    For(i,1,n){
        cin >> a[i];
        maxx += a[i] > 0;
    }
    sgt t = sgt(n + q);
    For(i,1,n)
        t.add(a[i]);
    For(i,1,q){
        int x,v;
        cin >> x >> v;
        t.del(a[x]);
        maxx -= a[x] > 0;
        a[x] = v;
        t.add(a[x]);
        maxx += a[x] > 0;
        int pref = t.Q();
        if(pref == 0)
            pref = 0;
        else
            pref = n - pref + 1;
        cout << maxx - pref + 1 << '\n';
    }
    return 0;
}