#define _CRT_SECURE_NO_WARNINGS

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <cstring>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <list>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <unordered_set>
#include <unordered_map>
#include <array>
#include <cassert>
#include <bitset>
#include <cstdint>
using namespace std;
using LL = long long;

struct node {
	LL L, R, A, S;
	node(int x) {
		L = max(x, 0);
		R = max(x, 0);
		A = max(x, 0);
		S = x;
	}
	node operator+(const node& o) {
		node res(0);
		res.A = max(max(A, o.A), R + o.L);
		res.L = max(L, S + o.L);
		res.R = max(o.R, o.S + R);
		res.S = S + o.S;
		return res;
	}
};

//ただのセグ木
template<typename T>
class RMQ {
private:
	const T DEF;//デフォルト値(minではINF、sumでは0など)
	vector<T> seg;//生データ
	int width;//セグ木の幅(配列の大きさではない！)
	T query_raw(int a, int b, int k, int l, int r)const {
		if (a >= r || b <= l)return DEF;
		if (a <= l && r <= b)return seg[k];
		return query_raw(a, b, 2 * k + 1, l, (l + r) / 2) + query_raw(a, b, 2 * k + 2, (l + r) / 2, r);
	}
public:
	//サイズn、デフォルト値defのセグ木を作る
	RMQ(int n, T def) :DEF(def) {
		width = 1;
		while (width < n)width *= 2;
		seg.assign(width * 2 - 1, DEF);
	}
	//区間[a,b)のクエリの答えを取得する
	T query(int a, int b)const { return query_raw(a, b, 0, 0, width); }
	//x番目の要素をkに更新する
	void update(int k, T x) {
		k += width - 1;
		seg[k] = x;
		while (k > 0) {
			k = (k - 1) / 2;
			seg[k] = seg[2 * k + 1] + seg[2 * k + 2];
		}
	}
	//配列ごと初期化する
	void init(const vector<T>& vec) {
		for (int i = 0; i < min(width, (int)vec.size()); ++i)
			seg[i + width - 1] = vec[i];
		for (int k = width - 2; k >= 0; --k)
			seg[k] = seg[2 * k + 1] + seg[2 * k + 2];
	}
};

int N, Q;
LL A[123456];

int main() {
	cin >> N >> Q;
	RMQ<node>tree(N, node(0));
	for (int i = 0; i < N; ++i) {
		LL val;
		cin >> val;
		tree.update(i, node(val));
	}
	cout << tree.query(0, N).A << endl;
	for (int i = 0; i < Q; ++i) {
		LL k, x;
		cin >> k >> x;
		k--;
		tree.update(k, node(x));
		cout << tree.query(0, N).A << endl;
	}
	return 0;
}
