#include <cstdio>
#include <algorithm>
#define lc (p<<1)
#define rc (p<<1|1)
using namespace std;
int read(){
	char c=getchar();int x=0;bool f=0;
	while(c<48||c>57) f|=(c=='-'),c=getchar();
	do x=(x<<1)+(x<<3)+(c^48),c=getchar();
	while(c>=48&&c<=57);
	if(f) return -x;
	return x;
}
const int N=200003;
typedef long long ll;
const ll INF=0x3f3f3f3f3f3f3f3f;
int n,q;
ll c[N],w[N];
ll mn[N<<2],tg[N<<2],sm[N<<2];
void proc(int p,ll v){mn[p]+=v;tg[p]+=v;}
void pushdown(int p){
	if(tg[p]){
		proc(lc,tg[p]);
		proc(rc,tg[p]);
		tg[p]=0;
	}
}
void pushup(int p){
	mn[p]=min(mn[lc],mn[rc]);
	sm[p]=sm[lc]+sm[rc];
}
void build(int p=1,int l=1,int r=n){
	tg[p]=0;
	if(l==r){mn[p]=w[l];sm[p]=(c[l]>>1);return;}
	int mid=(l+r)>>1;
	build(lc,l,mid);
	build(rc,mid+1,r);
	pushup(p);
}
void update(int x,ll v,int p=1,int l=1,int r=n){
	if(x<=l) return proc(p,v);
	pushdown(p);
	int mid=(l+r)>>1;
	if(x>mid) update(x,v,rc,mid+1,r);
	else update(x,v,lc,l,mid),proc(rc,v);
	pushup(p);
}
void modify(int x,ll v,int p=1,int l=1,int r=n){
	if(l==r){sm[p]+=v;return;}
	pushdown(p);
	int mid=(l+r)>>1;
	if(x<=mid) modify(x,v,lc,l,mid);
	else modify(x,v,rc,mid+1,r);
	pushup(p);
}
ll pre,suf;
ll query(ll cur=0,ll tmp=INF,int p=1,int l=1,int r=n){
	if(l==r){pre=cur;suf=min(tmp,mn[p]);return l;}
	pushdown(p);
	int mid=(l+r)>>1;
	ll tmn=min(tmp,mn[rc]);
	if(tmn+(cur+sm[lc])*3>=0) return query(cur,tmn,lc,l,mid);
	else return query(cur+sm[lc],tmp,rc,mid+1,r);
}
int main(){
	n=read();q=read();
	for(int i=1;i<=n;++i){
		c[i]=read();
		if(c[i]&1) ++w[(i>>1)+1];
		w[i]-=(c[i]>>1);
	}
	for(int i=1;i<=n;++i) w[i]+=w[i-1];
	build();
	while(q--){
		int x=read(),v=read();
		if(v&1){
			if(c[x]&1) update((x>>1)+1,-1);
			else update((x>>1)+1,1);
		}
		modify(x,((c[x]+v)>>1)-(c[x]>>1));
		update(x,(c[x]>>1)-((c[x]+v)>>1));
		c[x]+=v;
		if(mn[1]>=0) printf("%lld\n",sm[1]);
		else{
			int t=query();
			ll num=c[t]>>1;
			printf("%lld\n",sm[1]-(-suf+2)/3);
		}
	}
	return 0;
}