#include <iostream>
#include <vector>
#include <array>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <tuple>
#include <bitset>
#include <memory>
#include <cmath>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <numeric>
#include <climits>
#include <cfloat>

class SegTree {
	static SegTree* make(const std::vector<long long int>& initial, const int from, const int until);
public:
	virtual ~SegTree() {};
	virtual void update(const int from, const int until, const long long int diff) = 0;
	virtual long long int min_of(const int from, const int until) = 0;
	virtual long long int max_of(const int from, const int until) = 0;
	static std::shared_ptr<SegTree> make(const std::vector<long long int>& initial);
};
class Leaf : public SegTree {
	int position;
	long long int value;
public:
	Leaf(const int pos, const long long int val) : position{ pos }, value{ val }{};
	void update(const int from, const int until, const long long int diff) override {
		if (from <= position && position < until) {
			value += diff;
		}
	}
	long long int min_of(const int from, const int until) override {
		if (from <= position && position < until) return value;
		else return LLONG_MAX;
	}
	long long int max_of(const int from, const int until) override {
		if (from <= position && position < until) return value;
		else return LLONG_MIN;
	}
};
class Branch : public SegTree {
	int from_position, until_position;
	long long int min_cache, max_cache;
	SegTree* left, * right;
	long long int operation = 0;
	void update_inner() {
		if (operation != 0) {
			left->update(from_position, until_position, operation);
			right->update(from_position, until_position, operation);
			operation = 0;
		}
		min_cache = std::min(left->min_of(from_position, until_position), right->min_of(from_position, until_position));
		max_cache = std::max(left->max_of(from_position, until_position), right->max_of(from_position, until_position));
	}
public:
	Branch(const int from, const int until, SegTree* l, SegTree* r) :
		from_position{ from }, until_position{ until },
		left{ l }, right{ r },
		min_cache{ std::min(l->min_of(from, until), r->min_of(from, until)) }, max_cache{ std::max(l->max_of(from, until), r->max_of(from, until)) }{};
	~Branch() {
		delete left, right;
	}
	void update(const int from, const int until, const long long int diff) override {
		if (until <= from_position || until_position <= from) return;
		else if (from <= from_position && until_position <= until) operation += diff;
		else {
			left->update(from, until, diff);
			right->update(from, until, diff);
			update_inner();
		}
	}
	long long int min_of(const int from, const int until) override {
		if (until <= from_position || until_position <= from) return LLONG_MAX;
		else if (from <= from_position && until_position <= until) return min_cache + operation;
		else return std::min(left->min_of(from, until), right->min_of(from, until)) + operation;
	}
	long long int max_of(const int from, const int until) override {
		if (until <= from_position || until_position <= from) return LLONG_MIN;
		else if (from <= from_position && until_position <= until) return max_cache + operation;
		else return std::max(left->max_of(from, until), right->max_of(from, until)) + operation;
	}
};



int main() {
	int n, q; std::cin >> n >> q;
	std::vector<int> series(n, 0);
	for (auto& a : series) std::cin >> a;
	std::vector<long long int> sum_array(n + 1, 0);
	for (auto i = 0; i < n; ++i) {
		sum_array[i + 1] = sum_array[i] + series[i];
	}
	auto seg_tree = SegTree::make(sum_array);
	auto comparator = [](const std::pair<int, long long int>& a, const std::pair<int, long long int>& b) {return a.second < b.second; };
	std::priority_queue<std::pair<int, long long int>, std::vector<std::pair<int, long long int>>, decltype(comparator)> queue(comparator);
	for (auto i = 1; i <= n; ++i) {
		queue.emplace(i, seg_tree->max_of(i, n + 1) - seg_tree->min_of(0, i));
	}
	std::cout << std::max(0LL, queue.top().second) << '\n';
	for (auto i = 0; i < q; ++i) {
		int k, x; std::cin >> k >> x;
		seg_tree->update(k, n + 1, x - series[k - 1]);
		if (x > series[k - 1]) {
			queue.emplace(k, seg_tree->max_of(k, n + 1) - seg_tree->min_of(0, k));
		}
		else {
			queue.emplace(k + 1, seg_tree->max_of(k + 1, n + 1) - seg_tree->min_of(0, k + 1));
		}
		while (true) {
			auto top = queue.top();
			const auto max_subsequence = seg_tree->max_of(top.first, n + 1) - seg_tree->min_of(0, top.first);
			if (top.second == max_subsequence) break;
			queue.emplace(top.first, max_subsequence);
			queue.pop();
		}
		series[k - 1] = x;
		std::cout << std::max(0LL, queue.top().second) << '\n';
	}
}

SegTree* SegTree::make(const std::vector<long long int>& initial, const int from, const int until)
{
	if (from + 1 == until) return new Leaf(from, initial[from]);
	else return new Branch(from, until, make(initial, from, (from + until) / 2), make(initial, (from + until) / 2, until));
}

std::shared_ptr<SegTree> SegTree::make(const std::vector<long long int>& initial)
{
	return std::shared_ptr<SegTree>(make(initial, 0, initial.size()));
}




Measured memory_bytes: 17568