#include<bits/stdc++.h> using namespace std; #define int long long #define pii pair<int,int> #define fr first #define sc second #define mk make_pair #define pb push_back #define inx(u) int I=h[(u)],v=edge[I].v,w=edge[I].w;I;I=edge[I].nx,v=edge[I].v,w=edge[I].w int read(){int 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<<1)+(x<<3)+(c^48),c=getchar();return x*f;} const int MAXN=200010; int n,m,k,q,a[MAXN],b[MAXN]; pii p[MAXN]; struct segtree{ #define lson (pos<<1) #define rson (pos<<1|1) struct node{ int x,y; }t[MAXN<<2],lz[MAXN<<2]; void pushup(int pos){ t[pos].x=min(t[lson].x,t[rson].x); t[pos].y=min(t[lson].y,t[rson].y); } void upd(int pos,int x,int y){ t[pos].x+=x,t[pos].y+=y; lz[pos].x+=x,lz[pos].y+=y; } void pushdown(int pos){ upd(lson,lz[pos].x,lz[pos].y),upd(rson,lz[pos].x,lz[pos].y),lz[pos]={0,0}; } void update(int pos,int l,int r,int ql,int qr,int x,int y){ if(ql<=l&&qr>=r){ upd(pos,x,y); return; } int mid=(l+r)>>1;pushdown(pos); if(ql<=mid)update(lson,l,mid,ql,qr,x,y); if(qr>mid)update(rson,mid+1,r,ql,qr,x,y); pushup(pos); } int query(int pos,int l,int r,int x){ // cout<<l<<" "<<r<<" "<<x<<" "<<t[pos].x<<" "<<t[pos].y<<endl; if(l==r)return x>0?l:l+1; int mid=(l+r)>>1;pushdown(pos); if(t[lson].y<=min(x,t[rson].x))return query(lson,l,mid,min(x,t[rson].x)); else return query(rson,mid+1,r,x); } int query(int pos,int l,int r,int ql,int qr){ if(ql<=l&&qr>=r)return t[pos].x; int mid=(l+r)>>1;pushdown(pos); if(qr<=mid)return query(lson,l,mid,ql,qr); if(ql>mid)return query(rson,mid+1,r,ql,qr); return min(query(lson,l,mid,ql,qr),query(rson,mid+1,r,ql,qr)); } void prt(int pos,int l,int r){ if(l==r){ cout<<t[pos].x<<","<<t[pos].y<<" "; return; } int mid=(l+r)>>1;pushdown(pos); prt(lson,l,mid),prt(rson,mid+1,r); } }T; struct treearray{ #define lb(x) ((x)&(-x)) int C[MAXN]; void upd(int x,int y){for(int i=x;i<=n;i+=lb(i))C[i]+=y;} int qry(int x){int res=0;for(int i=x;i>=1;i-=lb(i))res+=C[i];return res;} int qry(int l,int r){return qry(r)-qry(l-1);} void upd(int l,int r,int x){upd(l,x),upd(r+1,-x);} }A,B; void slv(){ n=read(),q=read(); for(int i=1;i<=n;i++){ a[i]=read(); if(a[i]&1)T.update(1,1,n,i/2+1,n,1,0),B.upd(i/2+1,n,1),m++; T.update(1,1,n,i,n,-(a[i]>>1),-(a[i]>>1)); A.upd(i,a[i]>>1); } while(q--){ int i=read(),y=read(); if(a[i]&1)T.update(1,1,n,i/2+1,n,-1,0),B.upd(i/2+1,n,-1),m--; T.update(1,1,n,i,n,a[i]>>1,a[i]>>1); A.upd(i,-(a[i]>>1)); a[i]+=y; if(a[i]&1)T.update(1,1,n,i/2+1,n,1,0),B.upd(i/2+1,n,1),m++; T.update(1,1,n,i,n,-(a[i]>>1),-(a[i]>>1)); A.upd(i,a[i]>>1); int it=T.query(1,1,n,0),ans=A.qry(it,n); // T.prt(1,1,n);cout<<endl; // cout<<it<<endl; if(it<=n){ // cout<<B.qry(it-1)<<" "<<A.qry(it-1,it-1)<<endl; ans+=min(B.qry(it-1),T.query(1,1,n,it,n)+A.qry(1,it-1)); } else ans+=B.qry(it-1); printf("%lld\n",((ans+2*A.qry(n))/3)); } } signed main(){ // freopen("1.in","r",stdin);freopen("1.out","w",stdout); slv(); // cerr<<clock()*1.0/CLOCKS_PER_SEC<<"s\n"; return 0; }