#include <bits/stdc++.h>
// #include "atcoder/modint"

using i64 = long long;
// using Fp = atcoder::modint998244353;

int op(int a, int b) {
    return std::min(a, b);
}
int e() {
    return 0;
}
int mapping(int a, int b) {
    return a + b;
}
int composition(int a, int b) {
    return a + b;
}
int id() {
    return 0;
}

class LazySegTree {
    int n, size, log;
    std::vector<int> data, lazy;

    void upd(int i) {
        data[i] = op(data[2 * i], data[2 * i + 1]);
    }
    void app(int k, int f) {
        data[k] = mapping(f, data[k]);
        if (k < size) lazy[k] = composition(f, lazy[k]);
    }
    void push(int k) {
        app(2 * k, lazy[k]);
        app(2 * k + 1, lazy[k]);
        lazy[k] = id();
    }

    public:
    LazySegTree(int n_) : n(n_) {
        log = 1;
        while ((1 << log) < n) ++log;
        size = 1 << log;
        data.assign(2 * size, e());
        lazy.assign(size, id());
    }

    int fold(int l, int r) {
        if (l == r) return e();
        l += size;
        r += size;
        for (int d = log; d >= 1; --d) {
            if (((l >> d) << d) != l) push(l >> d);
            if (((r >> d) << d) != r) push((r - 1) >> d);
        }

        int ret = 1 << 30;
        while (l < r) {
            if (l % 2 == 1) ret = op(ret, data[l++]);
            if (r % 2 == 1) ret = op(ret, data[--r]);
            l /= 2;
            r /= 2;
        }
        return ret;
    }

    int allfold() {
        return data[1];
    }

    void apply(int l, int r, int f) {
        l += size;
        r += size;
        for (int d = log; d >= 1; --d) {
            if (((l >> d) << d) != l) push(l >> d);
            if (((r >> d) << d) != r) push((r - 1) >> d);
        }

        int l2 = l, r2 = r;
        while (l < r) {
            if (l % 2 == 1) app(l++, f);
            if (r % 2 == 1) app(--r, f);
            l /= 2;
            r /= 2;
        }
        l = l2;
        r = r2;

        for (int d = 1; d <= log; ++d) {
            if (((l >> d) << d) != l) upd(l >> d);
            if (((r >> d) << d) != r) upd((r - 1) >> d);
        }
    }

    int get(int i) {
        return fold(i, i + 1);
    }

    void set(int i, int v) {
        apply(i, i + 1, v - get(i));
    }
};

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int N, Q;
    std::cin >> N >> Q;
    std::vector<i64> C(N + 1);
    for (int i = 1; i <= N; ++i) {
        std::cin >> C[i];
    }

    std::vector<i64> L(Q), D(Q);
    for (int i = 0; i < Q; ++i) {
        std::cin >> L[i] >> D[i];
    }

    /*
    if (N <= 2000 and Q <= 2000) {
        for (int q = 0; q < Q; ++q) {
            C[L[q]] += D[q];

            std::vector<int> O;
            for (int i = 1; i <= N; ++i) {
                if (C[i] % 2 == 1) {
                    O.push_back(i);
                }
            }
            auto D = C;
            for (auto &e : D) e = e / 2;

            int i = N;
            std::reverse(O.begin(), O.end());
            i64 ans = 0;
            for (const auto s : O) {
                while (i != 0 and D[i] == 0) --i;
                const int l = s / 2 + 1;
                if (i >= l) {
                    --D[i];
                    ++ans;
                }
            }
            i64 sum = 0;
            for (auto e : D) sum += e;
            ans += sum * 2 / 3;
            std::cout << ans << std::endl;
        }
        return 0;
    }
    */
    // subtask 3
    std::multiset<int> a, b, x, y;
    i64 s1 = 0;
    for (int i = 1; i <= N; ++i) {
        if (C[i] % 2 == 1) a.insert(i);
    }
    for (int i = N; i >= 1; --i) {
        i64 d = C[i];
        while (x.size() <= N + Q and d - 2 >= 0) {
            d -= 2;
            x.insert(i);
        }
        s1 += d / 2;
    }
    int p = 0;

    LazySegTree seg(N + 1);
    for (int i = 0; i <= N; ++i) seg.set(i, 0);
    while (true) {
        if (a.empty() or x.empty()) break;
        const int u = *a.begin(), v = *x.rbegin();
        seg.apply((u / 2) + 1, N + 1, 1);
        seg.apply(v, N + 1, -1);
        if (seg.allfold() < 0) {
            seg.apply((u / 2) + 1, N + 1, -1);
            seg.apply(v, N + 1, 1);
            break;
        } else {
            ++p;
            a.erase(a.find(u));
            x.erase(x.find(v));
            b.insert(u);
            y.insert(v);
        }
    }

    /*
    for (const auto e : a) std::cerr << e << ' ';
    std::cerr << std::endl;
    for (const auto e : b) std::cerr << e << ' ';
    std::cerr << std::endl;
    for (const auto e : x) std::cerr << e << ' ';
    std::cerr << std::endl;
    for (const auto e : y) std::cerr << e << ' ';
    std::cerr << std::endl;
    */

    auto upd = [&]() {
        while (seg.allfold() < 0) {
            const int u = *b.rbegin(), v = *y.begin();
            seg.apply((u / 2) + 1, N + 1, -1);
            seg.apply(v, N + 1, 1);
            --p;
            b.erase(b.find(u));
            y.erase(y.find(v));
            a.insert(u);
            x.insert(v);
        }
        while (true) {
            if (a.empty() or x.empty()) break;
            const int u = *a.begin(), v = *x.rbegin();
            seg.apply((u / 2) + 1, N + 1, 1);
            seg.apply(v, N + 1, -1);
            if (seg.allfold() < 0) {
                seg.apply((u / 2) + 1, N + 1, -1);
                seg.apply(v, N + 1, 1);
                break;
            } else {
                ++p;
                a.erase(a.find(u));
                x.erase(x.find(v));
                b.insert(u);
                y.insert(v);
            }
        }
    };

    auto erase = [&](int v, bool bx) {
        if (bx) {
            if (a.find(v) != a.end()) {
                a.erase(a.find(v));
            }
            if (b.find(v) != b.end()) {
                seg.apply((v / 2) + 1, N + 1, -1);
                const int o = *y.begin();
                seg.apply(o, N + 1, 1);
                y.erase(y.find(o));
                x.insert(o);
                b.erase(b.find(v));
                --p;
            }
            return;
        }
        if (x.find(v) != x.end()) {
            x.erase(x.find(v));
        }
        if (y.find(v) != y.end()) {
            seg.apply(v, N + 1, 1);
            const int o = *b.rbegin();
            seg.apply((o / 2) + 1, N + 1, -1);
            b.erase(b.find(o));
            a.insert(o);
            y.erase(y.find(v));
            --p;
        }
    };


    auto rollback = [&]() {
        if (b.empty()) return;
        const int u = *b.rbegin(), v = *y.begin();
        seg.apply((u / 2) + 1, N + 1, -1);
        seg.apply(v, N + 1, 1);
        --p;
        b.erase(b.find(u));
        y.erase(y.find(v));
        a.insert(u);
        x.insert(v);
    };

    auto adda = [&](int v) {
        a.insert(v);
        rollback();
        upd();
    };

    auto addx = [&](int v) {
        x.insert(v);
        rollback();
        upd();
    };

    for (int q = 0; q < Q; ++q) {
        if (C[L[q]] % 2 == 1) {
            erase(L[q], true);
        } else {
            if (C[L[q]] >= 2 and D[q] == -1) {
                if (x.find(L[q]) == x.end() and y.find(L[q]) == y.end()) {
                    --s1;
                } else erase(L[q], false);
            }
        }
        //td::cerr << p << std::endl;
        C[L[q]] += D[q];
        if (C[L[q]] % 2 == 1) adda(L[q]);
        else if (D[q] == 1) addx(L[q]);
        upd();
        std::cerr << x.size() << std::endl;
        std::cout << p + (x.size() + s1) * 2 / 3 << '\n';
    }

    /*
    if (std::all_of(D.begin(), D.end(), [&](int v) {
        return std::abs(v) <= 1;
    })) {
        // subtask 4

    } else {
        // subtask 3

    }
    */
}