#include <bits/stdc++.h>
using namespace std;
//#include "testlib.h"
#define ff first
#define ss second
#define mp make_pair
#define all(v) v.begin(),v.end()
#define int long long
#define ll long long
#define M 1000000007
#define inputarr(a,n) for(int i=0;i<n;++i) cin>>a[i]
#define GCD(m,n) __gcd(m,n)
#define LCM(m,n) m*(n/GCD(m,n))
#define mii map<ll ,ll >
#define sz(a) (int)a.size()
#define msi map<string,ll >
#define mis map<ll int, string>
#define rep(a,b) for(ll i=a;i<b;i++)
#define rep0(n) for(ll i=0;i<n;i++)
#define repi(i,a,b) for(ll i=a;i<b;i++)
#define pb push_back
#define vi vector<ll>
#define mp make_pair
#define vs vector<string>
#define ppb pop_back
#define endl '\n'
#define asdf ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define r0 return 0;
#define FORD(i, a, b) for (int i = (int) (a); i >= (int) (b); --i)
#define FORE(it, c) for (__typeof((c).begin()) it = (c).begin(); it != (c).end(); ++it)
#define inputoutput freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);
#define input freopen("input.txt", "r", stdin);
#define Set(a, s) 4(a, s, sizeof (a))
#define FOR repi
#define pii pair<int,int>
#define REVERSE(v) reverse(ALL(v))
#define display(x) trav(a,x) cout<<a<<" ";cout<<endl
#define debug cerr<<"bhau"<<endl
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
std::cerr << name << " : " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
const char* comma = strchr(names + 1, ',');std::cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
ll max(ll a, ll b) { return (a > b)? a : b;}
int min(int a, int b) { return (a < b)? a : b;}
void amax(int &a,int b){a=max(a,b)%M; }
void amin(int &a,int b){ a=min(a,b)%M;}
void inc(int &a,int b){a=(a+b)%M;}
void dec(int &a,int b){a=(a-b+M)%M;}
const int N=2e5+100,inf=0;
int total[2*N];
int pre[2*N];
int suff[2*N];
int ans[2*N];
int n;
void build(){
for(int i=n-1;i>=0;i--) {total[i]=total[i<<1]+total[i<<1|1];pre[i]=max(pre[i<<1],total[i<<1]+pre[i<<1|1]);suff[i]=max(suff[i<<1|1],suff[i<<1]+total[i<<1|1]);ans[i]=max({ans[i<<1],ans[i<<1|1],pre[i<<1|1]+suff[i<<1]});}
}
void modify(int p,int x){
p+=n;
for(total[p]=suff[p]=pre[p]=ans[p]=x;p>1;p>>=1) {
total[p>>1]=total[p]+total[p^1];
int right=max(p,p^1),left=min(p,p^1);
pre[p>>1]=max(pre[left],total[left]+pre[right]);
suff[p>>1]=max(suff[right],suff[left]+total[right]);
ans[p>>1]=max({ans[left],ans[right],pre[right]+suff[left]});
// trace(p>>1,p,p^1,total[p>>1],pre[p>>1],suff[p>>1],ans[p>>1]);
}
}
int query(int l,int r){
int tl,tr;tl=tr=0;
int pl,pr;
pl=pr=inf;
pr=inf;
int al,ar;
al=ar=inf;
int sl=inf,sr=inf;
for(l+=n,r+=n;l<r;l>>=1,r>>=1){
// trace(l,r);
if(l&1) {
al=max({al,ans[l],sl+pre[l]});
pl=max(pl,tl+pre[l]);
sl=max(suff[l],total[l]+sl);
tl+=total[l];
l++;
}
if(r&1) {
--r;
ar=max({ar,ans[r],sr+pre[r]});
pr=max(pre[r],total[r]+pr);
sr=max(sr,tr+suff[r]);
tr+=total[r];
}
// trace(pl,pr,sl,sr,al,ar,tl,tr);
}
int res;
res=max({al,ar,pr+sl});
return res;
}
int solve()
{
int q;cin>>n>>q;
rep0(n) cin>>total[i+n];
rep0(n) {pre[i]=suff[i]=ans[i]=inf;pre[n+i]=suff[n+i]=ans[n+i]=total[n+i];}
build();
while(q--){
int k,x;cin>>k>>x;k--;
modify(k,x);
cout<<query(0,n)<<endl;
}
r0
}
signed main()
{
asdf
int t=1;
//cin>>t;
while(t--)
{
solve();
}
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CiAKICAgIHVzaW5nIG5hbWVzcGFjZSBzdGQ7CiAgICAvLyNpbmNsdWRlICJ0ZXN0bGliLmgiCiAgICAjZGVmaW5lIGZmIGZpcnN0CiAgICAjZGVmaW5lIHNzIHNlY29uZAogICAgI2RlZmluZSBtcCBtYWtlX3BhaXIKICAgICNkZWZpbmUgYWxsKHYpIHYuYmVnaW4oKSx2LmVuZCgpCiAgICAjZGVmaW5lIGludCBsb25nIGxvbmcKICAgICNkZWZpbmUgbGwgbG9uZyBsb25nCiAgICAjZGVmaW5lIE0gMTAwMDAwMDAwNwogICAgI2RlZmluZSBpbnB1dGFycihhLG4pIGZvcihpbnQgaT0wO2k8bjsrK2kpIGNpbj4+YVtpXQogICAgI2RlZmluZSBHQ0QobSxuKSBfX2djZChtLG4pCiAgICAjZGVmaW5lIExDTShtLG4pIG0qKG4vR0NEKG0sbikpCiAgICAjZGVmaW5lIG1paSAgbWFwPGxsICxsbCA+CiAgICAjZGVmaW5lIHN6KGEpIChpbnQpYS5zaXplKCkKICAgICNkZWZpbmUgbXNpICBtYXA8c3RyaW5nLGxsID4KICAgICNkZWZpbmUgbWlzICBtYXA8bGwgaW50LCBzdHJpbmc+CiAgICAjZGVmaW5lIHJlcChhLGIpICAgIGZvcihsbCBpPWE7aTxiO2krKykKICAgICNkZWZpbmUgcmVwMChuKSAgICBmb3IobGwgaT0wO2k8bjtpKyspCiAgICAjZGVmaW5lIHJlcGkoaSxhLGIpIGZvcihsbCBpPWE7aTxiO2krKykKICAgICNkZWZpbmUgcGIgcHVzaF9iYWNrCiAgICAjZGVmaW5lIHZpIHZlY3RvcjxsbD4KICAgICNkZWZpbmUgbXAgbWFrZV9wYWlyCiAgICAjZGVmaW5lIHZzIHZlY3RvcjxzdHJpbmc+CiAgICAjZGVmaW5lIHBwYiBwb3BfYmFjawogICAgI2RlZmluZSBlbmRsICdcbicKICAgICNkZWZpbmUgYXNkZiBpb3NfYmFzZTo6c3luY193aXRoX3N0ZGlvKGZhbHNlKTtjaW4udGllKDApO2NvdXQudGllKDApOwogICAgI2RlZmluZSByMCByZXR1cm4gMDsKICAgICNkZWZpbmUgRk9SRChpLCBhLCBiKSBmb3IgKGludCBpID0gKGludCkgKGEpOyBpID49IChpbnQpIChiKTsgLS1pKQogICAgI2RlZmluZSBGT1JFKGl0LCBjKSBmb3IgKF9fdHlwZW9mKChjKS5iZWdpbigpKSBpdCA9IChjKS5iZWdpbigpOyBpdCAhPSAoYykuZW5kKCk7ICsraXQpCiAgICAjZGVmaW5lIGlucHV0b3V0cHV0IGZyZW9wZW4oImlucHV0LnR4dCIsICJyIiwgc3RkaW4pO2ZyZW9wZW4oIm91dHB1dC50eHQiLCAidyIsIHN0ZG91dCk7CiAgICAjZGVmaW5lIGlucHV0IGZyZW9wZW4oImlucHV0LnR4dCIsICJyIiwgc3RkaW4pOwogICAgI2RlZmluZSBTZXQoYSwgcykgNChhLCBzLCBzaXplb2YgKGEpKQogICAgI2RlZmluZSBGT1IgcmVwaQogICAgI2RlZmluZSBwaWkgcGFpcjxpbnQsaW50PgogICAgI2RlZmluZSBSRVZFUlNFKHYpIHJldmVyc2UoQUxMKHYpKQogICAgI2RlZmluZSBkaXNwbGF5KHgpIHRyYXYoYSx4KSBjb3V0PDxhPDwiICI7Y291dDw8ZW5kbAogICAgI2RlZmluZSBkZWJ1ZyBjZXJyPDwiYmhhdSI8PGVuZGwKICAgICNkZWZpbmUgdHJhY2UoLi4uKSBfX2YoI19fVkFfQVJHU19fLCBfX1ZBX0FSR1NfXykKICAgIHRlbXBsYXRlIDx0eXBlbmFtZSBBcmcxPgogICAgdm9pZCBfX2YoY29uc3QgY2hhciogbmFtZSwgQXJnMSYmIGFyZzEpewogICAgICAgIHN0ZDo6Y2VyciA8PCBuYW1lIDw8ICIgOiAiIDw8IGFyZzEgPDwgZW5kbDsKICAgIH0KICAgIHRlbXBsYXRlIDx0eXBlbmFtZSBBcmcxLCB0eXBlbmFtZS4uLiBBcmdzPgogICAgdm9pZCBfX2YoY29uc3QgY2hhciogbmFtZXMsIEFyZzEmJiBhcmcxLCBBcmdzJiYuLi4gYXJncyl7CiAgICAgICAgY29uc3QgY2hhciogY29tbWEgPSBzdHJjaHIobmFtZXMgKyAxLCAnLCcpO3N0ZDo6Y2Vyci53cml0ZShuYW1lcywgY29tbWEgLSBuYW1lcykgPDwgIiA6ICIgPDwgYXJnMTw8IiB8ICI7X19mKGNvbW1hKzEsIGFyZ3MuLi4pOwogICAgfQogICAgbGwgbWF4KGxsIGEsIGxsIGIpIHsgcmV0dXJuIChhID4gYik/IGEgOiBiO30KICAgIGludCBtaW4oaW50IGEsIGludCBiKSB7IHJldHVybiAoYSA8IGIpPyBhIDogYjt9CiAgICB2b2lkIGFtYXgoaW50ICZhLGludCBiKXthPW1heChhLGIpJU07IH0KICAgIHZvaWQgYW1pbihpbnQgJmEsaW50IGIpeyBhPW1pbihhLGIpJU07fQogICAgdm9pZCBpbmMoaW50ICZhLGludCBiKXthPShhK2IpJU07fQogICAgdm9pZCBkZWMoaW50ICZhLGludCBiKXthPShhLWIrTSklTTt9CiAgICBjb25zdCBpbnQgTj0yZTUrMTAwLGluZj0wOwogICAgaW50IHRvdGFsWzIqTl07CiAgICBpbnQgcHJlWzIqTl07CiAgICBpbnQgc3VmZlsyKk5dOwogICAgaW50IGFuc1syKk5dOwogICAgaW50IG47CiAgICB2b2lkIGJ1aWxkKCl7CiAgICAgIGZvcihpbnQgaT1uLTE7aT49MDtpLS0pIHt0b3RhbFtpXT10b3RhbFtpPDwxXSt0b3RhbFtpPDwxfDFdO3ByZVtpXT1tYXgocHJlW2k8PDFdLHRvdGFsW2k8PDFdK3ByZVtpPDwxfDFdKTtzdWZmW2ldPW1heChzdWZmW2k8PDF8MV0sc3VmZltpPDwxXSt0b3RhbFtpPDwxfDFdKTthbnNbaV09bWF4KHthbnNbaTw8MV0sYW5zW2k8PDF8MV0scHJlW2k8PDF8MV0rc3VmZltpPDwxXX0pO30KICAgIH0KICAgIHZvaWQgbW9kaWZ5KGludCBwLGludCB4KXsKICAgICAgcCs9bjsKICAgICAgZm9yKHRvdGFsW3BdPXN1ZmZbcF09cHJlW3BdPWFuc1twXT14O3A+MTtwPj49MSkgewogICAgICAgIAogICAgICAgIHRvdGFsW3A+PjFdPXRvdGFsW3BdK3RvdGFsW3BeMV07CiAgICAgICAgaW50IHJpZ2h0PW1heChwLHBeMSksbGVmdD1taW4ocCxwXjEpOwogICAgICAgIHByZVtwPj4xXT1tYXgocHJlW2xlZnRdLHRvdGFsW2xlZnRdK3ByZVtyaWdodF0pOwogICAgICAgIHN1ZmZbcD4+MV09bWF4KHN1ZmZbcmlnaHRdLHN1ZmZbbGVmdF0rdG90YWxbcmlnaHRdKTsKICAgICAgICBhbnNbcD4+MV09bWF4KHthbnNbbGVmdF0sYW5zW3JpZ2h0XSxwcmVbcmlnaHRdK3N1ZmZbbGVmdF19KTsKICAgICAgICAvLyB0cmFjZShwPj4xLHAscF4xLHRvdGFsW3A+PjFdLHByZVtwPj4xXSxzdWZmW3A+PjFdLGFuc1twPj4xXSk7CiAgICAgIH0KICAgIH0KICAgIGludCBxdWVyeShpbnQgbCxpbnQgcil7CiAgICAgIGludCB0bCx0cjt0bD10cj0wOwogICAgICBpbnQgcGwscHI7CiAgICAgIHBsPXByPWluZjsKICAgICAgcHI9aW5mOwogICAgICBpbnQgYWwsYXI7CiAgICAgIGFsPWFyPWluZjsKICAgICAgaW50IHNsPWluZixzcj1pbmY7CiAgICAgIGZvcihsKz1uLHIrPW47bDxyO2w+Pj0xLHI+Pj0xKXsKICAgICAgICAvLyB0cmFjZShsLHIpOwogICAgICAgIGlmKGwmMSkgewogICAgICAgICAgYWw9bWF4KHthbCxhbnNbbF0sc2wrcHJlW2xdfSk7CiAgICAgICAgICBwbD1tYXgocGwsdGwrcHJlW2xdKTsKICAgICAgICAgIHNsPW1heChzdWZmW2xdLHRvdGFsW2xdK3NsKTsKIAogICAgICAgICAgdGwrPXRvdGFsW2xdOwogICAgICAgICAgbCsrOwogICAgICAgIH0KICAgICAgICBpZihyJjEpIHsKICAgICAgICAgIC0tcjsKICAgICAgICAgIGFyPW1heCh7YXIsYW5zW3JdLHNyK3ByZVtyXX0pOwogICAgICAgICAgcHI9bWF4KHByZVtyXSx0b3RhbFtyXStwcik7CiAgICAgICAgICBzcj1tYXgoc3IsdHIrc3VmZltyXSk7CiAgICAgICAgICB0cis9dG90YWxbcl07CiAgICAgICAgfQogICAgICAgIC8vIHRyYWNlKHBsLHByLHNsLHNyLGFsLGFyLHRsLHRyKTsKICAgICAgfQogICAgICBpbnQgcmVzOwogICAgICByZXM9bWF4KHthbCxhcixwcitzbH0pOwogICAgICByZXR1cm4gcmVzOwogICAgfQogCiAgICAKICAgICBpbnQgc29sdmUoKQogICAgIHsgIAogICAgICAgIGludCBxO2Npbj4+bj4+cTsKICAgICAgICByZXAwKG4pIGNpbj4+dG90YWxbaStuXTsKICAgICAgICByZXAwKG4pIHtwcmVbaV09c3VmZltpXT1hbnNbaV09aW5mO3ByZVtuK2ldPXN1ZmZbbitpXT1hbnNbbitpXT10b3RhbFtuK2ldO30KICAgICAgICBidWlsZCgpOwogICAgICAgIHdoaWxlKHEtLSl7CiAgICAgICAgICBpbnQgayx4O2Npbj4+az4+eDtrLS07CiAgICAgICAgICBtb2RpZnkoayx4KTsKICAgICAgICAgIGNvdXQ8PHF1ZXJ5KDAsbik8PGVuZGw7CiAgICAgICAgfQogICAgICAgIHIwICAgCiAgICAgfQogICAgc2lnbmVkIG1haW4oKQogICAgeyAgIAogICAgICAgIGFzZGYKICAgICAgICAKICAgICAgICBpbnQgdD0xOwogICAgICAgIC8vY2luPj50OwogICAgICAgIHdoaWxlKHQtLSkKICAgICAgICB7CiAgICAgICAgICAgIHNvbHZlKCk7CiAgICAgICAgfSAgICAgCiAgICAgICAgCn0=