#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 1 << 30;
}
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;
    }

    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() {
    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::set<int> a, b, x, y;
    for (int i = 1; i <= N; ++i) {
        if (C[i] == 1) a.insert(i);
        if (C[i] == 2) x.insert(i);
    }
    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.fold(0, N + 1) < 0) {
            seg.apply((u / 2) + 1, N + 1, -1);
            seg.apply(v, N + 1, 1);
            break;
        } else {
            ++p;
            a.erase(u);
            x.erase(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.fold(0, N + 1) < 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(u);
            y.erase(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.fold(0, N + 1) < 0) {
                seg.apply((u / 2) + 1, N + 1, -1);
                seg.apply(v, N + 1, 1);
                break;
            } else {
                ++p;
                a.erase(u);
                x.erase(v);
                b.insert(u);
                y.insert(v);
            }
        }
    };

    auto erase = [&](int v) {
        if (a.find(v) != a.end()) {
            a.erase(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(o);
            x.insert(o);
            b.erase(v);
            --p;
        }
        if (x.find(v) != x.end()) {
            x.erase(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(o);
            a.insert(o);
            y.erase(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(u);
        y.erase(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) {
        erase(L[q]);
        C[L[q]] += D[q];
        if (C[L[q]] == 1) adda(L[q]);
        else if (C[L[q]] == 2) addx(L[q]);
        upd();
        std::cout << p + x.size() * 2 / 3 << std::endl;
    }

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

    } else {
        // subtask 3

    }
    */
}