Problem: E: Cut out the sum

problem

Ebi-chan has a sequence (a_1, a_2, ..., a_n). Ebi-chan is worried about the maximum value of the sum of the partial arrays (which may be empty), so please find it. Here, a subarray refers to a continuous subsequence. The sum of empty strings is 0.

In addition, Ebi-chan rewrites this sequence q times, so find this value immediately after each rewrite.

Input format


n q
a_1 a_2 ... a_n
k_1 x_1
...
k_q x_q


Each k_j, x_j (1 \ leq j \ leq q) means rewrite a_ {k_j} to x_j. Note that each rewrite is not independent and the array remains rewritten in subsequent processing.

Constraint

* 1 \ leq n \ leq 10 ^ 5
* 1 \ leq q \ leq 10 ^ 5
* 1 \ leq k_j \ leq n
* | a_i |, | x_j | \ leq 10 ^ 9



Output format

Please output q + 1 line. Output the maximum value of the sum of the subarrays before rewriting on the first line and immediately after the i-th rewrite on the 1 + i line.

Input example 1


5 2
1 2 -3 4 -5
3 3
2 -6


Output example 1


Four
Ten
7


If the subarray (a_l,…, a_r) is represented as a [l, r], the sum of a [1, 4] and a [4, 4] is 4 before rewriting, which is the maximum.

After the first rewrite, the sequence becomes (1, 2, 3, 4, -5), and the maximum sum is 10 of a [1, 4].

After the second rewrite, the sequence becomes (1, -6, 3, 4, -5) and the maximum sum is 7 in a [3, 4].

Input example 2


3 1
-one two Three
1 1


Output example 2


0
1


The sum of the empty strings is 0, which is the maximum before rewriting.





Example

Input

5 2
1 2 -3 4 -5
3 3
2 -6


Output

4
10
7

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
#define whlie while
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define rep(i,N) for(int i = 0; i < (N); i++)
#define repr(i,N) for(int i = (N) - 1; i >= 0; i--)
#define rep1(i,N) for(int i = 1; i <= (N) ; i++)
#define repr1(i,N) for(int i = (N) ; i > 0 ; i--)
#define each(x,v) for(auto& x : v)
#define all(v) (v).begin(),(v).end()
#define sz(v) ((int)(v).size())
#define vrep(v,it) for(auto it = v.begin(); it != v.end(); it++)
#define vrepr(v,it) for(auto it = v.rbegin(); it != v.rend(); it++)
#define ini(...) int __VA_ARGS__; in(__VA_ARGS__)
#define inl(...) ll __VA_ARGS__; in(__VA_ARGS__)
#define ins(...) string __VA_ARGS__; in(__VA_ARGS__)
using namespace std; void solve();
using ll = long long; using vl = vector<ll>;
using vi = vector<int>; using vvi = vector< vector<int> >;
constexpr int inf = 1001001001;
constexpr ll infLL = (1LL << 61) - 1;
struct IoSetupNya {IoSetupNya() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(15); cerr << fixed << setprecision(7);} } iosetupnya;
template<typename T, typename U> inline bool amin(T &x, U y) { return (y < x) ? (x = y, true) : false; }
template<typename T, typename U> inline bool amax(T &x, U y) { return (x < y) ? (x = y, true) : false; }
template<typename T, typename U> ostream& operator <<(ostream& os, const pair<T, U> &p) { os << p.first << " " << p.second; return os; }
template<typename T, typename U> istream& operator >>(istream& is, pair<T, U> &p) { is >> p.first >> p.second; return is; }
template<typename T> ostream& operator <<(ostream& os, const vector<T> &v) { int s = (int)v.size(); rep(i,s) os << (i ? " " : "") << v[i]; return os; }
template<typename T> istream& operator >>(istream& is, vector<T> &v) { for(auto &x : v) is >> x; return is; }
void in(){} template <typename T,class... U> void in(T &t,U &...u){ cin >> t; in(u...);}
void out(){cout << "\n";} template <typename T,class... U> void out(const T &t,const U &...u){ cout << t; if(sizeof...(u)) cout << " "; out(u...);}
template<typename T>void die(T x){out(x); exit(0);}
#ifdef NyaanDebug
  #include "NyaanDebug.h"
  #define trc(...) do { cerr << #__VA_ARGS__ << " = "; dbg_out(__VA_ARGS__);} while(0)
  #define trca(v,...) do { cerr << #v << " = "; array_out(v , __VA_ARGS__ );} while(0)
#else
  #define trc(...)
  #define trca(...)
  int main(){solve();}
#endif
 
using P = pair<ll,ll>; using vp = vector<P>;
constexpr int MOD = /**/ 1000000007; //*/ 998244353;
/////////////////

// セグ木
template<typename T,typename F>
struct ST{

  int size;
  vector<T> seg;
  const F func;
  const T UNIT;
  
  ST(int N,F func , T UNIT): func(func) , UNIT(UNIT) {
    size = 1;
    while(size < N) size <<= 1;
    seg.assign(2 * size, UNIT);
  }

  ST(const vector<T> &v,F func , T UNIT) : func(func) , UNIT(UNIT){
    // initialize
    int N = (int)v.size();
    size = 1;
    while(size < N) size <<= 1;
    seg.assign(2 * size , UNIT);
    // set
    for(int i = 0; i < N; i++){
      seg[i + size] = v[i];
    }
    build();
  }

  void set(int k, T x){
    seg[k + size] = x;
  }

  void build(){
    for(int k = size-1; k > 0; k--){
      seg[k] = func(seg[2 * k] , seg[2 * k + 1] );
    }
  }
  
  void update(int k, T x){
    k += size; seg[k] = x;
    while(k >>= 1){
      seg[k] = func( seg[2 * k] , seg[2 * k + 1] );
    }
  }

  void add(int k , T x){
    k += size; seg[k] += x;
    while(k >>= 1){
      seg[k] = func(seg[2 * k] , seg[2 * k + 1] );
    }
  }
  
  // 半開区間[a,b)へのクエリ
  T query(int a, int b){
    T L = UNIT, R = UNIT;
    for(a+=size,b+=size; a<b; a>>=1,b>>=1){
      if(a & 1) L = func(L,seg[a++]);
      if(b & 1) R = func(seg[--b],R);
    }
    return func(L, R);
  }

  T operator[](const int &k) const{
    return seg[k + size];
  }

};

// 左　不可能　右　全体の和
using T = tuple<ll,ll,ll,ll>;
auto func = [](T l,T r) -> T{
  ll a=max(get<0>(l),get<3>(l) + get<0>(r));
  ll c=max(get<2>(l)+get<3>(r) , get<2>(r));
  ll d= get<3>(l) + get<3>(r);
  ll b=max({a,c,d,get<1>(l),get<1>(r),get<2>(l)+get<0>(r)});
  return make_tuple(a,b,c,d);
};
T UNIT = make_tuple(0LL,0LL,0LL,0LL);
using SEG = ST<T , decltype(func)>;

void solve(){
  ini(N,Q);
  SEG seg(N , func , UNIT);
  rep(i,N){
    inl(x);ll y = max(0LL , x);
    seg.set(i , T(y,y,y,x));
  }
  seg.build();
  
  auto ret = seg.query(0,N);
  out(max(
    {get<0>(ret),get<1>(ret),get<2>(ret),get<3>(ret)}
  ));
  rep(i,Q){
    ini(k); inl(x); ll y = max(0LL , x);
    seg.update(k - 1 , T(y,y,y,x));
    auto ret = seg.seg[1];
    out(max(
      {get<0>(ret),get<1>(ret),get<2>(ret),get<3>(ret)}
    ));
  }
}