#include <bits/stdc++.h>

using namespace std;

class SegTree {
private:
    int n;
    vector<int> val, cnt, lazy;

    void push(int x, int l, int r) {
        if (lazy[x] == 0) return;
        val[x] += lazy[x];
        if (l != r) {
            lazy[x * 2] += lazy[x];
            lazy[x * 2 + 1] += lazy[x];
        }
        lazy[x] = 0;
    }

    void merge(int x) {
        if (val[x*2] == val[x*2+1]) {
            val[x] = val[x*2];
            cnt[x] = cnt[x*2] + cnt[x*2+1];
        } else if (val[x*2] < val[x*2+1]) {
            val[x] = val[x*2];
            cnt[x] = cnt[x*2];
        } else {
            val[x] = val[x*2+1];
            cnt[x] = cnt[x*2+1];
        }
    }

    void recount(int x, int tl, int tr, int pos, int delta) {
        push(x, tl, tr);
        if (tl == tr) {
            cnt[x] += delta;
            return;
        }
        int tm = (tl + tr) / 2;
        if (pos <= tm) {
            recount(x * 2, tl, tm, pos, delta);
            push(x * 2 + 1, tm + 1, tr);
        } else {
            push(x * 2, tl, tm);
            recount(x * 2 + 1, tm + 1, tr, pos, delta);
        }
        merge(x);
    }

    void update(int x, int tl, int tr, int l, int r, int val) {
        push(x, tl, tr);
        if (l > r) return;
        if (l == tl && tr == r) {
            lazy[x] += val;
            push(x, tl, tr);
            return;
        }
        int tm = (tl + tr) / 2;
        update(x * 2, tl, tm, l, min(r, tm), val);
        update(x * 2 + 1, tm + 1, tr, max(tm + 1, l), r, val);
        merge(x);
    }

    int query(int x, int tl, int tr, int l, int r) {
        push(x, tl, tr);
        if (l == tl && tr == r) {
            return val[x] == 1 ? cnt[x] : 0;
        }
        int tm = (tl + tr) / 2;
        if (r <= tm) {
            return query(x * 2, tl, tm, l, r);
        } else if (l > tm) {
            return query(x * 2 + 1, tm + 1, tr, l, r);
        } else {
            return query(x * 2, tl, tm, l, tm) +
                    query(x * 2 + 1, tm + 1, tr, tm + 1, r);
        }
    }
public:
    inline void update(int l, int r, int val) {
        update(1, 0, n - 1, l, r, val);
    }

    inline int query(int l, int r) {
        return query(1, 0, n - 1, l, r);
    }

    inline void recount(int pos, int val) {
        recount(1, 0, n - 1, pos, val);
    }

    SegTree(int n) : n(n), val(4*n), cnt(4*n), lazy(4*n) {}
};

int main() {
    ios_base::sync_with_stdio(false);

    int n, q; cin >> n >> q;
    vector<int> a(n + 2);
    int mx = 0;
    for (int i = 0; i < n; ++i) {
        cin >> a[i+1];
        mx = max(mx, a[i+1]);
    }
    a[n+1] = 0;
    vector<int> pos(q), x(q);
    for (int i = 0; i < q; ++i) {
        cin >> pos[i] >> x[i];
        mx = max(mx, x[i]);
    }
    a[0] = mx+1;

    ++n;
    SegTree segTree(a[0] + 1);

    auto addDiff = [&](int a, int b, int sgn) {
        if (a == b) return;
        segTree.update(min(a, b), max(a, b) - 1, sgn);
    };

    for (int i = 0; i < n; ++i) {
        addDiff(a[i], a[i + 1], +1);
        segTree.recount(a[i], +1);
    }
    for (int i = 0; i < q; ++i) {
        int p = pos[i], y = x[i];
        segTree.recount(a[p], -1);
        addDiff(a[p - 1], a[p], -1);
        addDiff(a[p], a[p + 1], -1);
        segTree.recount(y, +1);
        addDiff(a[p - 1], y, +1);
        addDiff(y, a[p + 1], +1);
        a[p] = y;
        cout << segTree.query(1, a[0] - 1) << "\n";
    }
}