#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;
}