#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <bitset>
#include <vector>
#include <algorithm>
#include <random>
#include <map>
#include <set>
#include <deque>
#include <cassert>
const int N = 5e5 + 7, A = 26, MOD = 1e9+7, C = 2;
using namespace std;

#define int long long

long long a[N];
int n, q;

struct Node {
    long long val[4]; // 00 01 10 11
};

Node merge(Node l, Node r) {
    Node ans;
    ans.val[0] = max(l.val[0] + r.val[0], max(l.val[0] + r.val[2], l.val[1] + r.val[0]) );
    ans.val[1] = max(l.val[1] + r.val[1], max(l.val[0] + r.val[1], l.val[0] + r.val[3]) );
    ans.val[2] = max(l.val[2] + r.val[0], max(l.val[2] + r.val[2], l.val[3] + r.val[0]) );
    ans.val[3] = max(l.val[2] + r.val[1], max(l.val[2] + r.val[3], l.val[3] + r.val[1]) );
    return ans;
}

struct SegmentTree {
    vector<Node> tree;
    void build(int n) {
        int h = 1;
        while (h < n) {
            h *= 2;
        }
        h *= 2;
        tree.resize(h);
        for (int i = h - 1; i > 0; i--) {
            if (i >= h / 2) {
                tree[i].val[0] = 0;
                tree[i].val[1] = 0;
                tree[i].val[2] = 0;
                tree[i].val[3] = a[i - h/2];
            }
            else {
                tree[i] = merge(tree[i * 2], tree[i * 2 + 1]);
            }
        }
    }
    void upd(int v, int val) {
        a[v] = val;
        v += tree.size() / 2;
        tree[v].val[3] = val;
        v /= 2;
        while (v != 0) {
            tree[v] = merge(tree[v * 2], tree[v * 2 + 1]);
            v /= 2;
        }
    }
    long long mx() {
        return max(max(tree[1].val[0], tree[1].val[1]), max(tree[1].val[2], tree[1].val[3]));
    }
};

SegmentTree ST;

long long dp[N][2];

signed main()
{
#ifdef _DEBUG
    freopen("input.txt", "r", stdin);
#else
    std::ios::sync_with_stdio(false);
    cin.tie(0);
#endif
    cin >> n >> q;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    ST.build(n);
    for (int i = 0; i < q; i++) {
        int x, c;
        cin >> x >> c;
        x--;
        ST.upd(x, c);
        cout << ST.mx() << "\n";
    }
}