#include <bits/stdc++.h> using namespace std; typedef unsigned long long ull; typedef long long ll; typedef long double ld; #define fastio() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0) #define loop(i,a,b) for(int i=a;i<b;i++) #define test() int t;cin>>t;loop(test,1,t+1) #define pb push_back #define eb emplace_back #define mkp make_pair #define nl cout<<"\n" #define sp cout<<" " #define F first #define S second #define vi vector<int> #define vl vector<ll> #define pii pair<int,int> #define pll pair<ll,ll> #define vii vector<pii> #define vll vector<pll> #define MOD 1000000007 #define all(x) x.begin(),x.end() template<class C> void min_self( C &a, C b ){ a = min(a,b); } template<class C> void max_self( C &a, C b ){ a = max(a,b); } const int MAXN = 2e5+5; const int LOGN = 21; const ll INF = 1e14; typedef struct node { ll total, prefix, suffix, answer; node() { total = prefix = suffix = answer = 0; } void set( ll val ) { total = prefix = suffix = answer = val; } } node; node tree[2*MAXN]; ll a[MAXN]; int n,m; void merge( node &a, node b, node c ) { a.total = b.total + c.total; a.prefix = max( { 0ll, b.prefix, b.total + c.prefix } ); a.suffix = max( { 0ll, b.suffix + c.total, c.suffix } ); a.answer = max( { 0ll, b.answer, c.answer, b.suffix + c.prefix } ); } void update( int p, ll x ) { p += n; tree[p].set(x); for( ; p > 1 ; p >>= 1 ) { merge( tree[p>>1], tree[min(p, p^1)], tree[max(p, p^1)] ); } } ll query( int l, int r ) { node lans, rans; lans.set(-INF); rans.set(-INF); l += n, r += n; while( l < r ) { if( l&1 ) { merge( lans, lans, tree[l] ); l++; } if( r&1 ) { r--; merge( rans, tree[r], rans ); } l >>= 1; r >>= 1; } merge( lans, lans, rans ); return max( { lans.prefix, lans.suffix, lans.answer } ); } int main() { // #ifndef ONLINE_JUDGE // freopen("input.txt", "r", stdin); // freopen("output.txt", "w", stdout); // #endif fastio(); cin>>n>>m; for(int i=0;i<n;i++) { cin>>a[i]; update(i, a[i]); } for(int i=n-1;i>0;i--) { merge( tree[i], tree[i<<1], tree[i<<1|1] ); } while(m--) { int pos; ll x; cin>>pos>>x; pos--; update(pos, x); cout<<query(0,n),nl; } cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n"; return 0; }