#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <fstream>
#include <cassert>
#include <cstring>
#include <unordered_set>
#include <unordered_map>
#include <numeric>
#include <ctime>
#include <bitset>
#include <complex>
#include <random>
#include <functional>

using namespace std;

const int MAXN = 2e6 + 1;
const int INF = 1e9 + 239;

namespace ST {
    int t[4 * MAXN];
    int cnt[4 * MAXN];
    int mod[4 * MAXN];

    void pull(int v) {
        if (t[2 * v + 1] < t[2 * v + 2]) {
            t[v] = t[2 * v + 1];
            cnt[v] = cnt[2 * v + 1];
        } else if (t[2 * v + 1] > t[2 * v + 2]) {
            t[v] = t[2 * v + 2];
            cnt[v] = cnt[2 * v + 2];
        } else {
            t[v] = t[2 * v + 1];
            cnt[v] = cnt[2 * v + 1] + cnt[2 * v + 2];
        }
    }

    void apply(int v, int x) {
        t[v] += x;
        mod[v] += x;
    }

    void push(int v) {
        if (mod[v] != 0) {
            apply(2 * v + 1, mod[v]);
            apply(2 * v + 2, mod[v]);
            mod[v] = 0;
        }
    }

    void modify(int v, int l, int r, int ql, int qr, int val) {
        if (qr <= l || r <= ql) {
            return;
        } else if (ql <= l && r <= qr) {
            apply(v, val);
        } else {
            push(v);
            int m = (r + l) >> 1;
            modify(2 * v + 1, l, m, ql, qr, val);
            modify(2 * v + 2, m, r, ql, qr, val);
            pull(v);
        }
    }

    int cntmn() {
        return cnt[0];
    }

    void build(int v, int l, int r) {
        if (l + 1 == r) {
            cnt[v] = 1;
        } else {
            int m = (r + l) >> 1;
            build(2 * v + 1, l, m);
            build(2 * v + 2, m, r);
            pull(v);
        }
    }

    void init() {
        fill(t, t + 4 * MAXN, 0);
        fill(cnt, cnt + 4 * MAXN, 0);
        fill(mod, mod + 4 * MAXN, 0);
        build(0, 0, MAXN);
    }

    void add(int l, int r, int c) {
        r++;
        modify(0, 0, MAXN, l, r, c);
    }
}

void zip(vector<int> &a, vector<pair<int, int>> &qr) {
    vector<int> sn = a;
    for (auto [f, s] : qr) {
        sn.push_back(s);
    }
    sort(sn.begin(), sn.end());
    for (auto &t : a) {
        t = 2 * (lower_bound(sn.begin(), sn.end(), t) - sn.begin() + 1);
    }
    for (auto &[f, t] : qr) {
        t = 2 * (lower_bound(sn.begin(), sn.end(), t) - sn.begin() + 1);
    }
}

vector<int> my(int n, vector<int> a, vector<pair<int, int>> qr) {
    ST::init();
    zip(a, qr);
    a.insert(a.begin(), MAXN - 1);
    a.push_back(0);
    n += 2;
    auto add = [&](int i, int c) {
        int f = a[i];
        int s = a[i + 1];
        if (f > s) {
            swap(f, s);
        }
        ST::add(f, s, c);
    };
    auto add_scaner = [&](int val) {
        ST::add(val, val, -INF);
    };
    auto kill_scaner = [&](int val) {
        ST::add(val, val, INF);
    };
    auto solve = [&]() {
        return ST::cntmn();
    };
    for (int i = 0; i < MAXN; i++) {
        kill_scaner(i);
    }
    for (int i = 1; i + 1 < n; i++) {
        add_scaner(a[i] - 1);
    }
    for (int i = 0; i + 1 < n; i++) {
        add(i, 1);
    }
    vector<int> res;
    for (auto [pos, x] : qr) {
        pos++;
        add(pos - 1, -1);
        add(pos, -1);
        kill_scaner(a[pos] - 1);
        a[pos] = x;
        add(pos - 1, 1);
        add(pos, 1);
        add_scaner(a[pos] - 1);
        res.push_back(solve());
    }
    return res;
}

void read() {
    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    for (auto &t : a) {
        cin >> t;
    }
    vector<pair<int, int>> qr(q);
    for (auto &[pos, x] : qr) {
        cin >> pos >> x;
        pos--;
    }
    auto ans = my(n, a, qr);
    for (auto t : ans) {
        cout << t << ' ';
    }
    cout << endl;
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    read();
}