#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
struct segment{
long long seg, prefix, suffix, sum;
};
struct segtree{
int size;
vector <segment> res;
segment nothing = {0LL, 0LL, 0LL, 0LL};
segment merge(segment a, segment b){
return{
max(a.seg, max(b.seg, a.suffix + b.prefix)),
max(a.prefix, a.sum+b.prefix),
max(b.suffix, b.sum+a.suffix),
a.sum+b.sum
};
}
segment single(int v){
if (v > 0) return {v, v, v, v};
else return {0, 0, 0, v};
}
void initiate(int n){
size = 1;
while (size < n) size *= 2;
res.resize(2*size);
}
void build(vector<int> &a, int index, int start, int end){
if (end - start == 1){
if (start < a.size()){ // changed (int)res.size() to a.size()
res.at(index) = single(a[start]);
}
return;
}
int mid = (start + end)/2;
build(a, index*2+1, start, mid);
build(a, index*2+2, mid, end);
res.at(index) = merge(res.at(index*2+1), res.at(index*2+2));
}
void build(vector<int> &a){
build(a, 0, 0, size);
}
void set(int i, int v, int index, int start, int end){
if (end - start == 1){
res.at(index) = single(v);
return;
}
int mid = (start + end)/2;
if (i < mid){
set(i, v, index*2+1, start, mid);
}
else{
set(i, v, index*2+2, mid, end);
}
res[index] = merge(res[index*2+1], res[index*2+2]);
}
void set(int i, int v){
set(i, v, 0, 0, size);
}
segment calc(int l, int r, int index, int start, int end){
if (r <= start || end <= l) return nothing;
if (start >= l && end <= r) return res[index];
int mid = (start + end)/2;
segment s1 = calc(l, r, index*2+1, start, mid);
segment s2 = calc(l, r, index*2+2, mid, end);
return merge(s1, s2);
}
segment calc(int l, int r){
return calc(l, r, 0, 0, size);
}
};
int main() {
const int M = 1e9, N = 1e5; const bool submit = false;
int n = N, q = N;
if (ios_base::sync_with_stdio(0), cin.tie(0), submit)
cin >> n >> q;
segtree st; vector<int> numbers(n), index(q), value(q); vector<long long> ans;
if (st.initiate(n), submit) {
for (int i = 0; i < n; ++i)
cin >> numbers[i];
for (int i = 0; i < q; ++i)
cin >> index[i] >> value[i]; }
else {
const auto random_value = [](int min, int max) {
static mt19937 random(chrono::system_clock::now().time_since_epoch().count());
return uniform_int_distribution<int>(min,max)(random); };
for (int i = 0; i < n; ++i)
numbers[i] = random_value(-M,M);
for (int m = n-1, i = 0; i < q; ++i)
index[i] = random_value(0,m), value[i] = random_value(-M,M); }
st.build(numbers), ans.push_back(st.calc(0,n).seg);
for (int i = 0; i < q; ++i)
st.set(index[i],value[i]), ans.push_back(st.calc(0,n).seg);
if (submit)
for (auto a: ans)
cout << a << '\n'; }
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgojZGVmaW5lIGVuZGwgIlxuIgogIApzdHJ1Y3Qgc2VnbWVudHsKCWxvbmcgbG9uZyBzZWcsIHByZWZpeCwgc3VmZml4LCBzdW07Cn07ICAKICAKc3RydWN0IHNlZ3RyZWV7CgkKCWludCBzaXplOwoJdmVjdG9yIDxzZWdtZW50PiByZXM7CgkKCXNlZ21lbnQgbm90aGluZyA9IHswTEwsIDBMTCwgMExMLCAwTEx9OwoJCQoJc2VnbWVudCBtZXJnZShzZWdtZW50IGEsIHNlZ21lbnQgYil7CgkJcmV0dXJuewoJCQltYXgoYS5zZWcsIG1heChiLnNlZywgYS5zdWZmaXggKyBiLnByZWZpeCkpLAoJCQltYXgoYS5wcmVmaXgsIGEuc3VtK2IucHJlZml4KSwKCQkJbWF4KGIuc3VmZml4LCBiLnN1bSthLnN1ZmZpeCksCgkJCWEuc3VtK2Iuc3VtCgkJfTsKCX0KCQoJc2VnbWVudCBzaW5nbGUoaW50IHYpewoJCWlmICh2ID4gMCkgcmV0dXJuIHt2LCB2LCB2LCB2fTsKCQllbHNlIHJldHVybiB7MCwgMCwgMCwgdn07Cgl9CgkKCXZvaWQgaW5pdGlhdGUoaW50IG4pewoJCXNpemUgPSAxOwoJCXdoaWxlIChzaXplIDwgbikgc2l6ZSAqPSAyOwoJCXJlcy5yZXNpemUoMipzaXplKTsKCX0KCQoJdm9pZCBidWlsZCh2ZWN0b3I8aW50PiAmYSwgaW50IGluZGV4LCBpbnQgc3RhcnQsIGludCBlbmQpewoJCWlmIChlbmQgLSBzdGFydCA9PSAxKXsKCQkJaWYgKHN0YXJ0IDwgYS5zaXplKCkpeyAvLyBjaGFuZ2VkIChpbnQpcmVzLnNpemUoKSB0byBhLnNpemUoKQoJCQkJcmVzLmF0KGluZGV4KSA9IHNpbmdsZShhW3N0YXJ0XSk7CgkJCX0KCQkJcmV0dXJuOwoJCX0KCQkKCQlpbnQgbWlkID0gKHN0YXJ0ICsgZW5kKS8yOwoJCWJ1aWxkKGEsIGluZGV4KjIrMSwgc3RhcnQsIG1pZCk7CgkJYnVpbGQoYSwgaW5kZXgqMisyLCBtaWQsIGVuZCk7CgoJCXJlcy5hdChpbmRleCkgPSBtZXJnZShyZXMuYXQoaW5kZXgqMisxKSwgcmVzLmF0KGluZGV4KjIrMikpOwoJfQoJCgl2b2lkIGJ1aWxkKHZlY3RvcjxpbnQ+ICZhKXsKCQlidWlsZChhLCAwLCAwLCBzaXplKTsKCX0KCQoJdm9pZCBzZXQoaW50IGksIGludCB2LCBpbnQgaW5kZXgsIGludCBzdGFydCwgaW50IGVuZCl7CgkJaWYgKGVuZCAtIHN0YXJ0ID09IDEpewoJCQlyZXMuYXQoaW5kZXgpID0gc2luZ2xlKHYpOwoJCQlyZXR1cm47CgkJfQoJCQoJCWludCBtaWQgPSAoc3RhcnQgKyBlbmQpLzI7CgkJCgkJaWYgKGkgPCBtaWQpewoJCQlzZXQoaSwgdiwgaW5kZXgqMisxLCBzdGFydCwgbWlkKTsKCQl9CgkJZWxzZXsKCQkJc2V0KGksIHYsIGluZGV4KjIrMiwgbWlkLCBlbmQpOwoJCX0KCQkKCQlyZXNbaW5kZXhdID0gbWVyZ2UocmVzW2luZGV4KjIrMV0sIHJlc1tpbmRleCoyKzJdKTsKCX0KCQoJdm9pZCBzZXQoaW50IGksIGludCB2KXsKCQlzZXQoaSwgdiwgMCwgMCwgc2l6ZSk7Cgl9CgkKCXNlZ21lbnQgY2FsYyhpbnQgbCwgaW50IHIsIGludCBpbmRleCwgaW50IHN0YXJ0LCBpbnQgZW5kKXsKCQlpZiAociA8PSBzdGFydCB8fCBlbmQgPD0gbCkgcmV0dXJuIG5vdGhpbmc7CgkJaWYgKHN0YXJ0ID49IGwgJiYgZW5kIDw9IHIpIHJldHVybiByZXNbaW5kZXhdOwoJCQoJCWludCBtaWQgPSAoc3RhcnQgKyBlbmQpLzI7CgkJCgkJc2VnbWVudCBzMSA9IGNhbGMobCwgciwgaW5kZXgqMisxLCBzdGFydCwgbWlkKTsKCQlzZWdtZW50IHMyID0gY2FsYyhsLCByLCBpbmRleCoyKzIsIG1pZCwgZW5kKTsKCQkKCQlyZXR1cm4gbWVyZ2UoczEsIHMyKTsKCX0KCQoJc2VnbWVudCBjYWxjKGludCBsLCBpbnQgcil7CgkJcmV0dXJuIGNhbGMobCwgciwgMCwgMCwgc2l6ZSk7Cgl9Cn07ICAKCmludCBtYWluKCkgeyAKCQoJY29uc3QgaW50IE0gPSAxZTksIE4gPSAxZTU7IGNvbnN0IGJvb2wgc3VibWl0ID0gZmFsc2U7IAoKCWludCBuID0gTiwgcSA9IE47CgkKCWlmIChpb3NfYmFzZTo6c3luY193aXRoX3N0ZGlvKDApLCBjaW4udGllKDApLCBzdWJtaXQpCgkJY2luID4+IG4gPj4gcTsKCQkKCXNlZ3RyZWUgc3Q7IHZlY3RvcjxpbnQ+IG51bWJlcnMobiksIGluZGV4KHEpLCB2YWx1ZShxKTsgdmVjdG9yPGxvbmcgbG9uZz4gYW5zOwoJCSAKCWlmIChzdC5pbml0aWF0ZShuKSwgc3VibWl0KSB7CgkKCQlmb3IgKGludCBpID0gMDsgaSA8IG47ICsraSkKCQkJY2luID4+IG51bWJlcnNbaV07CgkJCgkJZm9yIChpbnQgaSA9IDA7IGkgPCBxOyArK2kpCgkJCWNpbiA+PiBpbmRleFtpXSA+PiB2YWx1ZVtpXTsgfQkKCWVsc2UgewoJCgkJY29uc3QgYXV0byByYW5kb21fdmFsdWUgPSBbXShpbnQgbWluLCBpbnQgbWF4KSB7CgkJCXN0YXRpYyBtdDE5OTM3IHJhbmRvbShjaHJvbm86OnN5c3RlbV9jbG9jazo6bm93KCkudGltZV9zaW5jZV9lcG9jaCgpLmNvdW50KCkpOyAKCQkJcmV0dXJuIHVuaWZvcm1faW50X2Rpc3RyaWJ1dGlvbjxpbnQ+KG1pbixtYXgpKHJhbmRvbSk7IH07CgkKCQlmb3IgKGludCBpID0gMDsgaSA8IG47ICsraSkKCQkJbnVtYmVyc1tpXSA9IHJhbmRvbV92YWx1ZSgtTSxNKTsKCQkKCQlmb3IgKGludCBtID0gbi0xLCBpID0gMDsgaSA8IHE7ICsraSkKCQkJaW5kZXhbaV0gPSByYW5kb21fdmFsdWUoMCxtKSwgdmFsdWVbaV0gPSByYW5kb21fdmFsdWUoLU0sTSk7IH0KCQoJc3QuYnVpbGQobnVtYmVycyksIGFucy5wdXNoX2JhY2soc3QuY2FsYygwLG4pLnNlZyk7CgkKCWZvciAoaW50IGkgPSAwOyBpIDwgcTsgKytpKQoJCXN0LnNldChpbmRleFtpXSx2YWx1ZVtpXSksIGFucy5wdXNoX2JhY2soc3QuY2FsYygwLG4pLnNlZyk7IAoJCQoJaWYgKHN1Ym1pdCkKCQlmb3IgKGF1dG8gYTogYW5zKQoJCQljb3V0IDw8IGEgPDwgJ1xuJzsgfQoJCQ==