/*
author: kartik8800
*/
#include<bits/stdc++.h>
#define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL)
#define ll long long
using namespace std;
#define left(i) (2*i + 1)
#define right(i) (2*i + 2)
#define parent(i) ((i-1)/2)
#include <vector>
template<class T>
class SegmentTree
{
public:
SegmentTree(std::vector<T> data, T value, T (*combine)(T obj1, T obj2));
SegmentTree(T ar[], int n, T value, T (*combine)(T obj1, T obj2));
T query(int l, int r);
void update(int idx, T val);
//TODO lazy propagation
private:
T *tree;
void buildTree(std::vector<T> data);
int segTreeSize;
T valueForExtraNodes;
T (*combine)(T obj1, T obj2);
int calculateSize(int n);
T queryHelper(int l,int r, int st, int ed, int node);
};
template<class T> SegmentTree<T>::SegmentTree(std::vector<T> data,
T value, T (*combine)(T obj1, T obj2))
{
this->combine = combine;
valueForExtraNodes = value;
segTreeSize = calculateSize(data.size());
buildTree(data);
}
template<class T> SegmentTree<T>::SegmentTree(T ar[], int n,
T value, T (*combine)(T obj1, T obj2))
{
this->combine = combine;
valueForExtraNodes = value;
segTreeSize = calculateSize(n);
std::vector<T> data;
for(int i = 0; i < n; i++)
data.push_back(ar[i]);
buildTree(data);
}
template<class T> int SegmentTree<T>::calculateSize(int n)
{
int pow2 = 1;
while( pow2 < n)
{
pow2 = pow2 << 1;
}
return 2*pow2 - 1;
}
template<class T> T SegmentTree<T>::query(int l, int r)
{
int st = 0, ed = segTreeSize/2;
return queryHelper(l, r, st, ed, 0);
}
template<class T> T SegmentTree<T>::queryHelper(int l,int r, int st, int ed, int node)
{
if( (r < st) || (l > ed) || (l > r) )
return valueForExtraNodes;
if(st >= l && ed <= r)
return tree[node];
T leftVal = queryHelper(l, r, st, (st + ed)/2, left(node));
T rightVal = queryHelper(l, r, (st+ed)/2 + 1, ed, right(node));
return combine(leftVal, rightVal);
}
template<class T> void SegmentTree<T>::buildTree(std::vector<T> data)
{
int n = data.size();
tree = new T[segTreeSize];
int extraNodes = (segTreeSize/2 + 1) - n;
for(int i = segTreeSize - 1; i >= 0; i--)
{
if(extraNodes>0)
{
tree[i] = valueForExtraNodes;
extraNodes--;
}
else if(n>0)
{
tree[i] = data[n-1];
n--;
}
else
tree[i] = combine(tree[left(i)], tree[right(i)]);
}
}
template<class T> void SegmentTree<T>::update(int idx, T val)
{
int segTreeIdx = (segTreeSize/2) + idx;
tree[segTreeIdx] = val;
while(parent(segTreeIdx) >= 0)
{
segTreeIdx = parent(segTreeIdx);
if(right(segTreeIdx) < segTreeSize)
tree[segTreeIdx] = combine(tree[left(segTreeIdx)], tree[right(segTreeIdx)]);
if(segTreeIdx == 0)
break;
}
}
// SEGMENT TREE NODE WITH REQUIRED INFO
struct node
{
ll maxSumSub;
ll sumOfAllElements;
ll prefix;
ll suffix;
node(){}
// For a leaf node, all these values are simply equal to A[x] if
// node represents range [x,x]
node(ll val)
{maxSumSub = sumOfAllElements = prefix = suffix = val;}
};
//Generate result for parent node using child nodes.
node combine(node x,node y)
{
node *ptr = new node();
// either left ans or right ans
ptr->maxSumSub = max(x.maxSumSub, y.maxSumSub);
// or of form suffix UNION prefix
ptr->maxSumSub = max(ptr->maxSumSub, x.suffix + y.prefix);
// as discussed
ptr->prefix = max(x.prefix, x.sumOfAllElements + y.prefix);
// as discussed
ptr->suffix = max(y.suffix, y.sumOfAllElements + x.suffix);
// sum of all elements of range [l,mid] and that of [mid+1,r]
ptr->sumOfAllElements = x.sumOfAllElements + y.sumOfAllElements;
return *ptr;
}
int main()
{
fast_io;
int t,i,j,n,ans,q;
cin>>n>>q;
vector<node> v(n);
for(i=0;i<n;i++)
{
cin>>j;
v[i] = node(j);
}
// combine( node_x, identityNode ) = node_x
// the problem says empty subarrays are allowed
// The minimum sum will be 0
node identityNode(0);
SegmentTree<node> sg(v,identityNode,combine);
while(q--)
{
cin>>i>>j;
sg.update(i-1,j);
node as = sg.query(0,n-1);
cout<<(as.maxSumSub)<<'\n';
}
return 0;
}
LyoKICAgIGF1dGhvcjoga2FydGlrODgwMAoqLwojaW5jbHVkZTxiaXRzL3N0ZGMrKy5oPgojZGVmaW5lIGZhc3RfaW8gaW9zX2Jhc2U6OnN5bmNfd2l0aF9zdGRpbyhmYWxzZSk7Y2luLnRpZShOVUxMKQojZGVmaW5lIGxsIGxvbmcgbG9uZwp1c2luZyBuYW1lc3BhY2Ugc3RkOwojZGVmaW5lIGxlZnQoaSkgKDIqaSArIDEpCiNkZWZpbmUgcmlnaHQoaSkgKDIqaSArIDIpCiNkZWZpbmUgcGFyZW50KGkpICgoaS0xKS8yKQojaW5jbHVkZSA8dmVjdG9yPgoKdGVtcGxhdGU8Y2xhc3MgVD4KY2xhc3MgU2VnbWVudFRyZWUKewogICAgcHVibGljOgogICAgICAgIFNlZ21lbnRUcmVlKHN0ZDo6dmVjdG9yPFQ+IGRhdGEsIFQgdmFsdWUsIFQgKCpjb21iaW5lKShUIG9iajEsIFQgb2JqMikpOwogICAgICAgIFNlZ21lbnRUcmVlKFQgYXJbXSwgaW50IG4sIFQgdmFsdWUsIFQgKCpjb21iaW5lKShUIG9iajEsIFQgb2JqMikpOwogICAgICAgIFQgcXVlcnkoaW50IGwsIGludCByKTsKICAgICAgICB2b2lkIHVwZGF0ZShpbnQgaWR4LCBUIHZhbCk7CiAgICAgICAgLy9UT0RPIGxhenkgcHJvcGFnYXRpb24KICAgIHByaXZhdGU6CiAgICAgICAgVCAqdHJlZTsKICAgICAgICB2b2lkIGJ1aWxkVHJlZShzdGQ6OnZlY3RvcjxUPiBkYXRhKTsKICAgICAgICBpbnQgc2VnVHJlZVNpemU7CiAgICAgICAgVCB2YWx1ZUZvckV4dHJhTm9kZXM7CiAgICAgICAgVCAoKmNvbWJpbmUpKFQgb2JqMSwgVCBvYmoyKTsKICAgICAgICBpbnQgY2FsY3VsYXRlU2l6ZShpbnQgbik7CiAgICAgICAgVCBxdWVyeUhlbHBlcihpbnQgbCxpbnQgciwgaW50IHN0LCBpbnQgZWQsIGludCBub2RlKTsKfTsKCnRlbXBsYXRlPGNsYXNzIFQ+IFNlZ21lbnRUcmVlPFQ+OjpTZWdtZW50VHJlZShzdGQ6OnZlY3RvcjxUPiBkYXRhLAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBUIHZhbHVlLCBUICgqY29tYmluZSkoVCBvYmoxLCBUIG9iajIpKQp7CiAgIHRoaXMtPmNvbWJpbmUgPSBjb21iaW5lOwogICB2YWx1ZUZvckV4dHJhTm9kZXMgPSB2YWx1ZTsKICAgc2VnVHJlZVNpemUgPSBjYWxjdWxhdGVTaXplKGRhdGEuc2l6ZSgpKTsKICAgYnVpbGRUcmVlKGRhdGEpOwp9Cgp0ZW1wbGF0ZTxjbGFzcyBUPiBTZWdtZW50VHJlZTxUPjo6U2VnbWVudFRyZWUoVCBhcltdLCBpbnQgbiwKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBUIHZhbHVlLCBUICgqY29tYmluZSkoVCBvYmoxLCBUIG9iajIpKQp7CiAgIHRoaXMtPmNvbWJpbmUgPSBjb21iaW5lOwogICB2YWx1ZUZvckV4dHJhTm9kZXMgPSB2YWx1ZTsKICAgc2VnVHJlZVNpemUgPSBjYWxjdWxhdGVTaXplKG4pOwoKICAgc3RkOjp2ZWN0b3I8VD4gZGF0YTsKICAgZm9yKGludCBpID0gMDsgaSA8IG47IGkrKykKICAgICAgICAgZGF0YS5wdXNoX2JhY2soYXJbaV0pOwoKICAgYnVpbGRUcmVlKGRhdGEpOwp9CgoKdGVtcGxhdGU8Y2xhc3MgVD4gaW50IFNlZ21lbnRUcmVlPFQ+OjpjYWxjdWxhdGVTaXplKGludCBuKQp7CiAgICBpbnQgcG93MiA9IDE7CiAgICB3aGlsZSggcG93MiA8IG4pCiAgICB7CiAgICAgICAgcG93MiA9IHBvdzIgPDwgMTsKICAgIH0KICAgIHJldHVybiAyKnBvdzIgLSAxOwp9Cgp0ZW1wbGF0ZTxjbGFzcyBUPiBUIFNlZ21lbnRUcmVlPFQ+OjpxdWVyeShpbnQgbCwgaW50IHIpCnsKICAgIGludCBzdCA9IDAsIGVkID0gc2VnVHJlZVNpemUvMjsKICAgIHJldHVybiBxdWVyeUhlbHBlcihsLCByLCBzdCwgZWQsIDApOwp9Cgp0ZW1wbGF0ZTxjbGFzcyBUPiBUIFNlZ21lbnRUcmVlPFQ+OjpxdWVyeUhlbHBlcihpbnQgbCxpbnQgciwgaW50IHN0LCBpbnQgZWQsIGludCBub2RlKQp7CiAgICBpZiggKHIgPCBzdCkgfHwgKGwgPiBlZCkgfHwgKGwgPiByKSApCiAgICAgICAgcmV0dXJuIHZhbHVlRm9yRXh0cmFOb2RlczsKICAgIGlmKHN0ID49IGwgJiYgZWQgPD0gcikKICAgICAgICByZXR1cm4gdHJlZVtub2RlXTsKICAgIFQgbGVmdFZhbCA9IHF1ZXJ5SGVscGVyKGwsIHIsIHN0LCAoc3QgKyBlZCkvMiwgbGVmdChub2RlKSk7CiAgICBUIHJpZ2h0VmFsID0gcXVlcnlIZWxwZXIobCwgciwgKHN0K2VkKS8yICsgMSwgZWQsIHJpZ2h0KG5vZGUpKTsKICAgIHJldHVybiBjb21iaW5lKGxlZnRWYWwsIHJpZ2h0VmFsKTsKfQoKdGVtcGxhdGU8Y2xhc3MgVD4gdm9pZCBTZWdtZW50VHJlZTxUPjo6YnVpbGRUcmVlKHN0ZDo6dmVjdG9yPFQ+IGRhdGEpCnsKICAgaW50IG4gPSBkYXRhLnNpemUoKTsKICAgdHJlZSA9IG5ldyBUW3NlZ1RyZWVTaXplXTsKICAgaW50IGV4dHJhTm9kZXMgPSAoc2VnVHJlZVNpemUvMiArIDEpIC0gbjsKICAgZm9yKGludCBpID0gc2VnVHJlZVNpemUgLSAxOyBpID49IDA7IGktLSkKICAgewogICAgICAgaWYoZXh0cmFOb2Rlcz4wKQogICAgICAgICAgIHsKICAgICAgICAgICAgICAgdHJlZVtpXSA9IHZhbHVlRm9yRXh0cmFOb2RlczsKICAgICAgICAgICAgICAgZXh0cmFOb2Rlcy0tOwogICAgICAgICAgIH0KICAgICAgIGVsc2UgaWYobj4wKQogICAgICAgICAgIHsKICAgICAgICAgICAgICAgdHJlZVtpXSA9IGRhdGFbbi0xXTsKICAgICAgICAgICAgICAgbi0tOwogICAgICAgICAgIH0KICAgICAgIGVsc2UKICAgICAgICAgICB0cmVlW2ldID0gY29tYmluZSh0cmVlW2xlZnQoaSldLCB0cmVlW3JpZ2h0KGkpXSk7CiAgIH0KfQoKdGVtcGxhdGU8Y2xhc3MgVD4gdm9pZCBTZWdtZW50VHJlZTxUPjo6dXBkYXRlKGludCBpZHgsIFQgdmFsKQp7CiAgICBpbnQgc2VnVHJlZUlkeCA9IChzZWdUcmVlU2l6ZS8yKSArIGlkeDsKICAgIHRyZWVbc2VnVHJlZUlkeF0gPSB2YWw7CiAgICB3aGlsZShwYXJlbnQoc2VnVHJlZUlkeCkgPj0gMCkKICAgIHsKICAgICAgICBzZWdUcmVlSWR4ID0gcGFyZW50KHNlZ1RyZWVJZHgpOwogICAgICAgIGlmKHJpZ2h0KHNlZ1RyZWVJZHgpIDwgc2VnVHJlZVNpemUpCiAgICAgICAgICB0cmVlW3NlZ1RyZWVJZHhdID0gY29tYmluZSh0cmVlW2xlZnQoc2VnVHJlZUlkeCldLCB0cmVlW3JpZ2h0KHNlZ1RyZWVJZHgpXSk7CiAgICAgICAgaWYoc2VnVHJlZUlkeCA9PSAwKQogICAgICAgICAgICBicmVhazsKICAgIH0KfQoKLy8gU0VHTUVOVCBUUkVFIE5PREUgV0lUSCBSRVFVSVJFRCBJTkZPCnN0cnVjdCBub2RlCnsKICAgIGxsIG1heFN1bVN1YjsKICAgIGxsIHN1bU9mQWxsRWxlbWVudHM7CiAgICBsbCBwcmVmaXg7CiAgICBsbCBzdWZmaXg7CiAgICBub2RlKCl7fQogICAgLy8gRm9yIGEgbGVhZiBub2RlLCBhbGwgdGhlc2UgdmFsdWVzIGFyZSBzaW1wbHkgZXF1YWwgdG8gQVt4XSBpZgogICAgLy8gbm9kZSByZXByZXNlbnRzIHJhbmdlIFt4LHhdCiAgICBub2RlKGxsIHZhbCkKICAgICAgICB7bWF4U3VtU3ViID0gc3VtT2ZBbGxFbGVtZW50cyA9IHByZWZpeCA9IHN1ZmZpeCA9IHZhbDt9Cn07CgovL0dlbmVyYXRlIHJlc3VsdCBmb3IgcGFyZW50IG5vZGUgdXNpbmcgY2hpbGQgbm9kZXMuCm5vZGUgY29tYmluZShub2RlIHgsbm9kZSB5KQp7CiAgICBub2RlICpwdHIgPSBuZXcgbm9kZSgpOwogICAgLy8gZWl0aGVyIGxlZnQgYW5zIG9yIHJpZ2h0IGFucwogICAgcHRyLT5tYXhTdW1TdWIgPSBtYXgoeC5tYXhTdW1TdWIsIHkubWF4U3VtU3ViKTsKICAgIC8vIG9yIG9mIGZvcm0gc3VmZml4IFVOSU9OIHByZWZpeAogICAgcHRyLT5tYXhTdW1TdWIgPSBtYXgocHRyLT5tYXhTdW1TdWIsIHguc3VmZml4ICsgeS5wcmVmaXgpOwogICAgLy8gYXMgZGlzY3Vzc2VkCiAgICBwdHItPnByZWZpeCA9IG1heCh4LnByZWZpeCwgeC5zdW1PZkFsbEVsZW1lbnRzICsgeS5wcmVmaXgpOwogICAgLy8gYXMgZGlzY3Vzc2VkCiAgICBwdHItPnN1ZmZpeCA9IG1heCh5LnN1ZmZpeCwgeS5zdW1PZkFsbEVsZW1lbnRzICsgeC5zdWZmaXgpOwogICAgLy8gc3VtIG9mIGFsbCBlbGVtZW50cyBvZiByYW5nZSBbbCxtaWRdIGFuZCB0aGF0IG9mIFttaWQrMSxyXQogICAgcHRyLT5zdW1PZkFsbEVsZW1lbnRzID0geC5zdW1PZkFsbEVsZW1lbnRzICsgeS5zdW1PZkFsbEVsZW1lbnRzOwogICAgcmV0dXJuICpwdHI7Cn0KCmludCBtYWluKCkKewogICAgZmFzdF9pbzsKICAgIGludCB0LGksaixuLGFucyxxOwoKICAgIGNpbj4+bj4+cTsKICAgIHZlY3Rvcjxub2RlPiB2KG4pOwoKICAgIGZvcihpPTA7aTxuO2krKykKICAgIHsKICAgICAgICBjaW4+Pmo7CiAgICAgICAgdltpXSA9IG5vZGUoaik7CiAgICB9CgogICAgLy8gY29tYmluZSggbm9kZV94LCBpZGVudGl0eU5vZGUgKSA9IG5vZGVfeAogICAgLy8gdGhlIHByb2JsZW0gc2F5cyBlbXB0eSBzdWJhcnJheXMgYXJlIGFsbG93ZWQKICAgIC8vIFRoZSBtaW5pbXVtIHN1bSB3aWxsIGJlIDAKICAgIG5vZGUgaWRlbnRpdHlOb2RlKDApOwogICAgU2VnbWVudFRyZWU8bm9kZT4gc2codixpZGVudGl0eU5vZGUsY29tYmluZSk7CgogICAgd2hpbGUocS0tKQogICAgewogICAgICAgIGNpbj4+aT4+ajsKICAgICAgICBzZy51cGRhdGUoaS0xLGopOwogICAgICAgIG5vZGUgYXMgPSBzZy5xdWVyeSgwLG4tMSk7CiAgICAgICAgY291dDw8KGFzLm1heFN1bVN1Yik8PCdcbic7CiAgICB9CiAgICByZXR1cm4gMDsKfQo=