#include<bits/stdc++.h>
using namespace::std;
const long long inf = 1e18;
struct node{
long long ans;
long long total;
long long prefix;
long long suffix;
node(){
ans = prefix = suffix = -inf;
total = 0;
}
node(int x){
ans = total = prefix = suffix = x;
}
node operator + (const node R){
node q;
q.ans = max(ans, max(R.ans, suffix + R.prefix));
q.suffix = max(R.suffix, R.total + suffix);
q.prefix = max(prefix, total + R.prefix);
q.total = total + R.total;
return q;
}
};
template<class T>
struct SegTree{
int n;
vector<T> st;
void set(vector<T> &a){
n = a.size();
st.assign(4 * n, 0);
for(int i = 0; i < n; i++) update(i, a[i]);
}
void update(int x, T y, int pos, int l, int r){
if(l == r){
st[pos] = y;
return;
}
int mi = (l + r) / 2;
if(x <= mi) update(x, y, 2 * pos, l, mi);
else update(x, y, 2 * pos + 1, mi + 1, r);
st[pos] = st[2 * pos] + st[2 * pos + 1];
}
T query(int x, int y, int pos, int l, int r){
if(y < l or r < x) return T();
if(x <= l and r <= y) return st[pos];
int mi = (l + r) / 2;
return query(x, y, 2 * pos, l, mi) + query(x, y, 2 * pos + 1, mi + 1, r);
}
void update(int x, T y){
update(x, y, 1, 0, n - 1);
}
T query(int x, int y){
return query(x, y, 1, 0, n - 1);
}
};
int main(){
int n, q;
scanf("%d %d", &n, &q);
vector<node> a(n);
for(int i = 0; i < n; i++){
int x;
scanf("%d", &x);
a[i] = node(x);
}
SegTree<node> st;
st.set(a);
printf("%lld\n", max(0ll, st.st[1].ans));
while(q--){
int i, v;
scanf("%d %d", &i, &v);
st.update(i, node(v));
printf("%lld\n", max(0ll, st.st[1].ans));
}
return 0;
}
I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KdXNpbmcgbmFtZXNwYWNlOjpzdGQ7Cgpjb25zdCBsb25nIGxvbmcgaW5mID0gMWUxODsKCnN0cnVjdCBub2RlewoJbG9uZyBsb25nIGFuczsKCWxvbmcgbG9uZyB0b3RhbDsKCWxvbmcgbG9uZyBwcmVmaXg7Cglsb25nIGxvbmcgc3VmZml4OwoJbm9kZSgpewoJCWFucyA9IHByZWZpeCA9IHN1ZmZpeCA9IC1pbmY7CgkJdG90YWwgPSAwOwoJfQoJbm9kZShpbnQgeCl7CgkJYW5zID0gdG90YWwgPSBwcmVmaXggPSBzdWZmaXggPSB4OwoJfQoKCW5vZGUgb3BlcmF0b3IgKyAoY29uc3Qgbm9kZSBSKXsKCQlub2RlIHE7CgkJcS5hbnMgPSBtYXgoYW5zLCBtYXgoUi5hbnMsIHN1ZmZpeCArIFIucHJlZml4KSk7CgkJcS5zdWZmaXggPSBtYXgoUi5zdWZmaXgsIFIudG90YWwgKyBzdWZmaXgpOwoJCXEucHJlZml4ID0gbWF4KHByZWZpeCwgdG90YWwgKyBSLnByZWZpeCk7CgkJcS50b3RhbCA9IHRvdGFsICsgUi50b3RhbDsKCQlyZXR1cm4gcTsKCX0KfTsKCnRlbXBsYXRlPGNsYXNzIFQ+CnN0cnVjdCBTZWdUcmVlewoJaW50IG47Cgl2ZWN0b3I8VD4gc3Q7CgoJdm9pZCBzZXQodmVjdG9yPFQ+ICZhKXsKCQluID0gYS5zaXplKCk7CgkJc3QuYXNzaWduKDQgKiBuLCAwKTsKCQlmb3IoaW50IGkgPSAwOyBpIDwgbjsgaSsrKSB1cGRhdGUoaSwgYVtpXSk7Cgl9CgkKCXZvaWQgdXBkYXRlKGludCB4LCBUIHksIGludCBwb3MsIGludCBsLCBpbnQgcil7CgkJaWYobCA9PSByKXsKCQkJc3RbcG9zXSA9IHk7CgkJCXJldHVybjsKCQl9CgkJaW50IG1pID0gKGwgKyByKSAvIDI7CgkJaWYoeCA8PSBtaSkgdXBkYXRlKHgsIHksIDIgKiBwb3MsIGwsIG1pKTsKCQllbHNlIHVwZGF0ZSh4LCB5LCAyICogcG9zICsgMSwgbWkgKyAxLCByKTsKCQlzdFtwb3NdID0gc3RbMiAqIHBvc10gKyBzdFsyICogcG9zICsgMV07Cgl9CgoJVCBxdWVyeShpbnQgeCwgaW50IHksIGludCBwb3MsIGludCBsLCBpbnQgcil7CgkJaWYoeSA8IGwgb3IgciA8IHgpIHJldHVybiBUKCk7CgkJaWYoeCA8PSBsIGFuZCByIDw9IHkpIHJldHVybiBzdFtwb3NdOwoJCWludCBtaSA9IChsICsgcikgLyAyOwoJCXJldHVybiBxdWVyeSh4LCB5LCAyICogcG9zLCBsLCBtaSkgKyBxdWVyeSh4LCB5LCAyICogcG9zICsgMSwgbWkgKyAxLCByKTsKCX0KCgl2b2lkIHVwZGF0ZShpbnQgeCwgVCB5KXsKCQl1cGRhdGUoeCwgeSwgMSwgMCwgbiAtIDEpOwoJfQoKCVQgcXVlcnkoaW50IHgsIGludCB5KXsKCQlyZXR1cm4gcXVlcnkoeCwgeSwgMSwgMCwgbiAtIDEpOwoJfQp9OwoKaW50IG1haW4oKXsKCWludCBuLCBxOwoJc2NhbmYoIiVkICVkIiwgJm4sICZxKTsKCXZlY3Rvcjxub2RlPiBhKG4pOwoJZm9yKGludCBpID0gMDsgaSA8IG47IGkrKyl7CgkJaW50IHg7CgkJc2NhbmYoIiVkIiwgJngpOwoJCWFbaV0gPSBub2RlKHgpOwoJfQoJU2VnVHJlZTxub2RlPiBzdDsKCXN0LnNldChhKTsKCXByaW50ZigiJWxsZFxuIiwgbWF4KDBsbCwgc3Quc3RbMV0uYW5zKSk7Cgl3aGlsZShxLS0pewoJCWludCBpLCB2OwoJCXNjYW5mKCIlZCAlZCIsICZpLCAmdik7CgkJc3QudXBkYXRlKGksIG5vZGUodikpOwoJCXByaW50ZigiJWxsZFxuIiwgbWF4KDBsbCwgc3Quc3RbMV0uYW5zKSk7Cgl9CglyZXR1cm4gMDsKfQ==