#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rrep(i, n) for (int i = (int)(n - 1); i >= 0; i--)
#define all(x) (x).begin(), (x).end()
#define sz(x) int(x.size())
using namespace std;
typedef long long ll;
const int INF = 1e9;
const ll MOD = 1e9 + 7;
const ll LINF = 1e18;
template <class T>
void get_unique(vector<T>& x) {
    x.erase(unique(x.begin(), x.end()), x.end());
}
template <class T>
bool chmax(T& a, const T& b) {
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool chmin(T& a, const T& b) {
    if (b < a) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
vector<T> make_vec(size_t a) {
    return vector<T>(a);
}
template <class T, class... Ts>
auto make_vec(size_t a, Ts... ts) {
    return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}
template <typename T>
ostream& operator<<(ostream& os, vector<T> v) {
    for (int i = 0; i < sz(v); i++) {
        os << v[i];
        if (i < sz(v) - 1) os << " ";
    }
    return os;
}
template <class T>
struct SegmentTreeBeats {
private:
    size_t n, n_;
    const T MAX = std::numeric_limits<T>::max();
    const T MIN = -MAX;
    std::vector<T> max_v, min_v, smax_v, smin_v, lz_upd, lz_ad, sigm, len;
    std::vector<int> max_c, min_c;

    void init(std::vector<T>& v) {
        n_ = v.size(), n = 1;
        while (n < n_) n *= 2;
        max_v.assign(n * 2 - 1, MIN);
        min_v.assign(n * 2 - 1, MAX);
        smax_v.assign(n * 2 - 1, MIN);
        smin_v.assign(n * 2 - 1, MAX);
        lz_upd.assign(n * 2 - 1, MAX);
        lz_ad.assign(n * 2 - 1, 0);
        len.assign(n * 2 - 1, n);
        sigm.assign(n * 2 - 1, 0);
        max_c.assign(n * 2 - 1, 1);
        min_c.assign(n * 2 - 1, 1);

        for (int i = 0; i < n - 1; i++)
            len[i * 2 + 1] = len[i * 2 + 2] = (len[i] >> 1);

        for (int i = 0; i < n_; i++)
            max_v[i + n - 1] = min_v[i + n - 1] = sigm[i + n - 1] = v[i];

        for (int i = n - 2; i >= 0; i--) proc(i);
    }

    void proc(int i) {
        sigm[i] = sigm[i * 2 + 1] + sigm[i * 2 + 2];

        max_v[i] = std::max(max_v[i * 2 + 1], max_v[i * 2 + 2]);

        if (max_v[i * 2 + 1] > max_v[i * 2 + 2]) {
            max_c[i] = max_c[i * 2 + 1];
            smax_v[i] = std::max(smax_v[i * 2 + 1], max_v[i * 2 + 2]);
        }

        if (max_v[i * 2 + 1] < max_v[i * 2 + 2]) {
            max_c[i] = max_c[i * 2 + 2];
            smax_v[i] = std::max(max_v[i * 2 + 1], smax_v[i * 2 + 2]);
        }

        if (max_v[i * 2 + 1] == max_v[i * 2 + 2]) {
            max_c[i] = max_c[i * 2 + 1] + max_c[i * 2 + 2];
            smax_v[i] = std::max(smax_v[i * 2 + 1], smax_v[i * 2 + 2]);
        }

        min_v[i] = std::min(min_v[i * 2 + 1], min_v[i * 2 + 2]);

        if (min_v[i * 2 + 1] < min_v[i * 2 + 2]) {
            min_c[i] = min_c[i * 2 + 1];
            smin_v[i] = std::min(smin_v[i * 2 + 1], min_v[i * 2 + 2]);
        }

        if (min_v[i * 2 + 1] > min_v[i * 2 + 2]) {
            min_c[i] = min_c[i * 2 + 2];
            smin_v[i] = std::min(min_v[i * 2 + 1], smin_v[i * 2 + 2]);
        }

        if (min_v[i * 2 + 1] == min_v[i * 2 + 2]) {
            min_c[i] = min_c[i * 2 + 1] + min_c[i * 2 + 2];
            smin_v[i] = std::min(smin_v[i * 2 + 1], smin_v[i * 2 + 2]);
        }
    }

    void eval(int i) {
        if (lz_upd[i] != MAX) {
            in_update(i * 2 + 1, lz_upd[i]);
            in_update(i * 2 + 2, lz_upd[i]);
            lz_upd[i] = MAX;
            return;
        }

        if (lz_ad[i]) {
            in_add(i * 2 + 1, lz_ad[i]);
            in_add(i * 2 + 2, lz_ad[i]);
            lz_ad[i] = 0;
        }

        if (max_v[i] < max_v[i * 2 + 1]) in_chmin(i * 2 + 1, max_v[i]);
        if (max_v[i] < max_v[i * 2 + 2]) in_chmin(i * 2 + 2, max_v[i]);

        if (min_v[i] > min_v[i * 2 + 1]) in_chmax(i * 2 + 1, min_v[i]);
        if (min_v[i] > min_v[i * 2 + 2]) in_chmax(i * 2 + 2, min_v[i]);
    }

    void in_update(int i, T x) {
        max_v[i] = min_v[i] = x;
        smax_v[i] = MIN, smin_v[i] = MAX;
        max_c[i] = min_c[i] = len[i];
        sigm[i] = len[i] * x;
        lz_upd[i] = x, lz_ad[i] = 0;
    }

    void in_chmin(int i, T x) {
        sigm[i] += (x - max_v[i]) * max_c[i];

        if (max_v[i] == min_v[i])
            max_v[i] = min_v[i] = x;

        else if (max_v[i] == smin_v[i])
            max_v[i] = smin_v[i] = x;

        else
            max_v[i] = x;

        if (lz_upd[i] != MAX and lz_upd[i] > x) lz_upd[i] = x;
    }

    void in_chmax(int i, T x) {
        sigm[i] += (x - min_v[i]) * min_c[i];

        if (min_v[i] == max_v[i])
            min_v[i] = max_v[i] = x;

        else if (min_v[i] == smax_v[i])
            min_v[i] = smax_v[i] = x;

        else
            min_v[i] = x;

        if (lz_upd[i] != MAX and lz_upd[i] < x) lz_upd[i] = x;
    }

    void in_add(int i, T x) {
        max_v[i] += x, min_v[i] += x;

        if (smin_v[i] != MAX) smin_v[i] += x;
        if (smax_v[i] != MIN) smax_v[i] += x;

        sigm[i] += x * len[i];

        if (lz_upd[i] != MAX) lz_upd[i] += x;
        lz_ad[i] += x;
    }

    void chmin(int i, int a, int b, int l, int r, T x) {
        if (b <= l or r <= a or x >= max_v[i]) return;

        if (a <= l and r <= b and smax_v[i] < x) {
            in_chmin(i, x);
            return;
        }

        eval(i);
        chmin(i * 2 + 1, a, b, l, (l + r) >> 1, x);
        chmin(i * 2 + 2, a, b, (l + r) >> 1, r, x);
        proc(i);
    }

    void chmax(int i, int a, int b, int l, int r, T x) {
        if (b <= l or r <= a or x <= min_v[i]) return;

        if (a <= l and r <= b and smin_v[i] > x) {
            in_chmax(i, x);
            return;
        }

        eval(i);
        chmax(i * 2 + 1, a, b, l, (l + r) >> 1, x);
        chmax(i * 2 + 2, a, b, (l + r) >> 1, r, x);
        proc(i);
    }

    void add(int i, int a, int b, int l, int r, T x) {
        if (b <= l or r <= a) return;

        if (a <= l and r <= b) {
            in_add(i, x);
            return;
        }

        eval(i);
        add(i * 2 + 1, a, b, l, (l + r) >> 1, x);
        add(i * 2 + 2, a, b, (l + r) >> 1, r, x);
        proc(i);
    }

    void update(int i, int a, int b, int l, int r, T x) {
        if (b <= l or r <= a) return;

        if (a <= l and r <= b) {
            in_update(i, x);
            return;
        }

        eval(i);
        update(i * 2 + 1, a, b, l, (l + r) >> 1, x);
        update(i * 2 + 2, a, b, (l + r) >> 1, r, x);
        proc(i);
    }

    T sum(int i, int a, int b, int l, int r) {
        if (r <= a || b <= l) return 0;
        if (a <= l && r <= b) return sigm[i];
        eval(i);
        T lv = sum(i * 2 + 1, a, b, l, (l + r) / 2);
        T rv = sum(i * 2 + 2, a, b, (l + r) / 2, r);
        return lv + rv;
    }

    T rangemin(int i, int a, int b, int l, int r) {
        if (r <= a or b <= l) return MAX;

        if (a <= l and r <= b) return min_v[i];

        eval(i);

        T lv = rangemin(i * 2 + 1, a, b, l, (l + r) >> 1);
        T rv = rangemin(i * 2 + 2, a, b, (l + r) >> 1, r);
        return std::min(lv, rv);
    }

    T rangemax(int i, int a, int b, int l, int r) {
        if (r <= a or b <= l) return MIN;

        if (a <= l and r <= b) return max_v[i];

        eval(i);

        T lv = rangemax(i * 2 + 1, a, b, l, (l + r) >> 1);
        T rv = rangemax(i * 2 + 2, a, b, (l + r) >> 1, r);
        return std::max(lv, rv);
    }

    T rangesum(int i, int a, int b, int l, int r) {
        if (r <= a or b <= l) return 0;

        if (a <= l and r <= b) return sigm[i];

        eval(i);

        T lv = rangesum(i * 2 + 1, a, b, l, (l + r) >> 1);
        T rv = rangesum(i * 2 + 2, a, b, (l + r) >> 1, r);
        return lv + rv;
    }

public:
    SegmentTreeBeats() = default;

    SegmentTreeBeats(std::vector<T>& v) {
        init(v);
    }

    SegmentTreeBeats(size_t n, T init_data) {
        std::vector<T> v(n, init_data);
        init(v);
    }

    void update_chmin(int a, int b, T x) {
        chmin(0, a, b, 0, n, x);
    }

    void update_chmax(int a, int b, T x) {
        chmax(0, a, b, 0, n, x);
    }

    void update_add(int a, int b, T x) {
        add(0, a, b, 0, n, x);
    }

    void update_upd(int a, int b, T x) {
        update(0, a, b, 0, n, x);
    }

    T query_min(int a, int b) {
        return rangemin(0, a, b, 0, n);
    }

    T query_max(int a, int b) {
        return rangemax(0, a, b, 0, n);
    }

    T query_sum(int a, int b) {
        return rangesum(0, a, b, 0, n);
    }
};
int main() {
    ll n, q;
    cin >> n >> q;
    SegmentTreeBeats<ll> tate(n, n - 1), yoko(n, n - 1);
    ll ans = (n - 2) * (n - 2);
    while (q--) {
        ll t, x;
        cin >> t >> x;
        x--;
        if (t == 1) {
            ll r = tate.query_max(x, x + 1);
            ans -= r - 1;
            yoko.update_chmin(0, r, x);
        }
        if (t == 2) {
            ll r = yoko.query_max(x, x + 1);
            ans -= r - 1;
            tate.update_chmin(0, r, x);
        }
    }
    cout << ans << '\n';
}

Measured memory_bytes: 78604