#include<bits/stdc++.h>
using namespace std;
using Int = long long;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}


struct FastIO{
  FastIO(){
    cin.tie(0);
    ios::sync_with_stdio(0);
  }
}fastio_beet;


template <typename T>
struct SegmentTree{
  using F = function<T(T,T)>;
  Int n;
  F f;
  T ti;
  vector<T> dat;
  SegmentTree(){};
  SegmentTree(F f,T ti):f(f),ti(ti){}
  void init(Int n_){
    n=1;
    while(n<n_) n<<=1;
    dat.assign(n<<1,ti);
  }
  void build(const vector<T> &v){
    Int n_=v.size();
    init(n_);
    for(Int i=0;i<n_;i++) dat[n+i]=v[i];
    for(Int i=n-1;i;i--)
      dat[i]=f(dat[(i<<1)|0],dat[(i<<1)|1]);
  }
  void set_val(Int k,T x){
    dat[k+=n]=x;
    while(k>>=1)
      dat[k]=f(dat[(k<<1)|0],dat[(k<<1)|1]);
  }
  T query(Int a,Int b){
    T vl=ti,vr=ti;
    for(Int l=a+n,r=b+n;l<r;l>>=1,r>>=1) {
      if(l&1) vl=f(vl,dat[l++]);
      if(r&1) vr=f(dat[--r],vr);
    }
    return f(vl,vr);
  }
  template<typename C>
  Int find(Int st,C &check,T &acc,Int k,Int l,Int r){
    if(l+1==r){
      acc=f(acc,dat[k]);
      return check(acc)?k-n:-1;
    }
    Int m=(l+r)>>1;
    if(m<=st) return find(st,check,acc,(k<<1)|1,m,r);
    if(st<=l&&!check(f(acc,dat[k]))){
      acc=f(acc,dat[k]);
      return -1;
    }
    Int vl=find(st,check,acc,(k<<1)|0,l,m);
    if(~vl) return vl;
    return find(st,check,acc,(k<<1)|1,m,r);
  }
  template<typename C>
  Int find(Int st,C &check){
    T acc=ti;
    return find(st,check,acc,1,0,n);
  }
};

//INSERT ABOVE HERE
signed main(){
  Int n,q;
  cin>>n>>q;
  vector<Int> as(n);
  for(Int i=0;i<n;i++) cin>>as[i];

  const Int INF = 1e15;
  using T = tuple<Int,Int,Int,Int,Int>;
  T ti(-INF,-INF,-INF,-INF,-INF);

  auto f=[&](T a,T b){
           if(a==ti) return b;
           if(b==ti) return a;
           Int as,ava,avi,avl,avr;
           tie(as,ava,avi,avl,avr)=a;
           Int bs,bva,bvi,bvl,bvr;
           tie(bs,bva,bvi,bvl,bvr)=b;
           Int cs=as+bs;
           Int cva=ava+bva,cvi=max(avi,bvi),cvl=avl,cvr=bvr;
           cvi=max(cvi,avr+bvl);
           cvl=max(cvl,ava+bvl);
           cvr=max(cvr,avr+bva);
           return T(cs,cva,cvi,cvl,cvr);
         };
  SegmentTree<T> seg(f,ti);

  vector<T> vt;
  for(Int i=0;i<n;i++) vt.emplace_back(as[i],as[i],as[i],as[i],as[i]);
  seg.build(vt);

  auto print=
    [&](){
      auto res=seg.query(0,n);
      Int ans=max({get<0>(res),get<1>(res),get<2>(res),get<3>(res),get<4>(res)});
      chmax(ans,0);
      cout<<ans<<endl;
    };

    print();
  for(Int i=0;i<q;i++){
    Int k,x;
    cin>>k>>x;
    k--;
    seg.set_val(k,T(x,x,x,x,x));
    print();
  }
  return 0;
}

