#include<bits/stdc++.h>
 
using namespace std;
 
#define LL long long int
#define FASTIO ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
const int oo = 1e9 + 5;
const LL ooll = (LL)1e18 + 5;
// const int MOD = 1e9 + 7;
const int MOD = 998244353;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define rand(l, r) uniform_int_distribution<int>(l, r)(rng)

clock_t start = clock();

const int N = 2e5 + 5;

int tree[8 * N], n, sz, lc[8 * N], rc[8 * N];

int construct_node() {
    tree[sz] = 0; 
    lc[sz] = rc[sz] = -1;
    sz++;
    return sz-1;
}

int build1(int st, int en) {
    int go = construct_node();
    if (st == en) {
        tree[go] = (st == n ? n : 0);
        return go;
    }
    int m = (st + en) >> 1;
    int lef = build1(st, m);
    int rig = build1(m+1, en);
    lc[go] = lef; rc[go] = rig;
    tree[go] = max(tree[lc[go]], tree[rc[go]]);
    return go;
}

void upd1(int pos, int val, int node, int st, int en) {
    if (st == en) {
        tree[node] = val;
        return;
    }
    int m = (st + en) >> 1;
    if (pos <= m) {
        upd1(pos, val, lc[node], st, m);
    } else {
        upd1(pos, val, rc[node], m+1, en);
    }
    tree[node] = max(tree[lc[node]], tree[rc[node]]);
}

int search(int x, int node, int st, int en) {
    if (st == en) {
        return st;
    }
    int m = (st + en) >> 1;
    if (tree[lc[node]] >= x) {
        return search(x, lc[node], st, m);
    }
    return search(x, rc[node], m+1, en);
}

int build2(int st, int en) {
    int go = construct_node();
    if (st == en) {
        tree[go] = 1;
        return go;
    }
    int m = (st + en) >> 1;
    int lef = build1(st, m);
    int rig = build1(m+1, en);
    lc[go] = lef; rc[go] = rig;
    tree[go] = 0;
    return go;
}

void upd2(int pos, int val, int node, int st, int en) {
    if (st == en) {
        tree[node] = val;
        return;
    }
    int m = (st + en) >> 1;
    if (pos <= m) {
        upd1(pos, val, lc[node], st, m);
    } else {
        upd1(pos, val, rc[node], m+1, en);
    }
    tree[node] = tree[lc[node]] + tree[rc[node]];
}

int qry2(int l, int r, int node, int st, int en) {
    if (en < l || st > r) {
        return 0;
    }
    if (st >= l && en <= r) {
        return tree[node];
    }
    int m = (st + en) >> 1;
    return qry2(l, r, lc[node], st, m) + qry2(l, r, rc[node], m+1, en);
}

int v[N], w[N];


template<class SegNode> struct SegTree {
    std::vector<SegNode> Tree;
    std::vector<int> lc, rc;
    int sz, L, R, rt;
    std::function<SegNode(SegNode, SegNode)> Merge;
    int construct_node() {
        sz++;
        Tree.push_back(SegNode());
        lc.push_back(-1); rc.push_back(-1);
        return sz-1;
    }
    void Lazy_Propagate(int node, int st, int en) {}
    void Lazy_Update(int node, SegNode val) {}
    SegTree() {
        sz = 0;
        Tree.clear();
        lc.clear();
        rc.clear();
    }
    SegTree(int L, int R, std::function<SegNode(SegNode, SegNode)> Merge) : L(L), R(R), Merge(Merge) {
        sz = 0;
        rt = construct_node();
    }
    SegTree(int L, int R, std::function<SegNode(SegNode, SegNode)> Merge, std::function<SegNode(int)> Init) : L(L), R(R), Merge(Merge) {
        sz = 0;
        rt = build_tree(L, R, Init);
    }
    int build_tree(int st, int en, std::function<SegNode(int)> &Init) {
        if (st == en) {
            int go = construct_node();
            Tree[go] = Init(st);
            return go;
        } 
        int m = (st + en) >> 1;
        int go = construct_node();
        int left_child = build_tree(st, m, Init);
        int right_child = build_tree(m+1, en, Init);
        lc[go] = left_child;
        rc[go] = right_child;
        Tree[go] = Merge(Tree[lc[go]], Tree[rc[go]]);
        return go;
    }
    void Pushdown(int node, int st, int en) {
        if (st < en) {
            if (lc[node] == -1) {
                int go = construct_node();
                lc[node] = go;
            }
            if (rc[node] == -1) {
                int go = construct_node();
                rc[node] = go;
            }
        }
        Lazy_Propagate(node, st, en);
    }
    void Point_Update(int pos, SegNode val, int node, int st, int en) {
        Pushdown(node, st, en);
        if (pos > en || pos < st) return;
        if (st == en) {
            Tree[node] = val;
            return;
        }
        int m = (st + en) >> 1;
        if (pos <= m) Point_Update(pos, val, lc[node], st, m);
        else Point_Update(pos, val, rc[node], m+1, en);
        Tree[node] = Merge(Tree[lc[node]], Tree[rc[node]]);
    }
    void Point_Update(int pos, SegNode val) {
        Point_Update(pos, val, rt, L, R);
    }
    SegNode Range_Query(int l, int r, int node, int st, int en) {
        Pushdown(node, st, en);
        if (st > r || en < l) return SegNode();
        if (st >= l && en <= r) return Tree[node];
        int m = (st + en) >> 1;
        return Merge(Range_Query(l, r, lc[node], st, m), Range_Query(l, r, rc[node], m+1, en));
    }
    SegNode Range_Query(int l, int r) {
        return Range_Query(l, r, rt, L, R);
    }
    void Range_Update(int l, int r, SegNode &val, int node, int st, int en) {
        Pushdown(node, st, en);
        if (st > r || en < l) return;
        if (st >= l && en <= r) {
            Lazy_Update(node, st, en, val);
            Lazy_Propagate(node, st, en);
            return;
        }
        int m = (st + en) >> 1;
        Range_Update(l, r, val, lc[node], st, m);
        Range_Update(l, r, val, rc[node], m+1, en);
        Tree[node] = Merge(Tree[lc[node]], Tree[rc[node]]);
    }
    void Range_Update(int l, int r, SegNode val) {
        return Range_Update(l, r, val, rt, L, R);
    }
    int Binary_Search(int x, int node, int st, int en); //{
    //     Pushdown(node, st, en);
    //     if (st == en) return st;
    //     int m = (st + en) >> 1;
    //     if (true) {
    //         return Binary_Search(x , rc[node], m+1, en);
    //     }
    //     return Binary_Search(x , lc[node], st, m);
    // }
    int Binary_Search(int x) {
        return Binary_Search(x, rt, L, R);
    }
    void Display(int node, int st, int en); // {
    //     cout << node << ": " << st << ',' << en << " = ";
    //     cout << '\n';
    //     if (st == en) return;
    //     Display(lc[node], st, m);
    //     Display(rc[node], m+1, en);
    // }
    void Display() {
        Display(rt, L, R);
    }
};

void solve() {
    cin >> n;
    sz = 0;
    int rt1 = build1(1, n);
    int rt2 = build1(1, n);
    int q;
    cin >> q;
    for (int i=1;i<=n;++i) v[i] = 0; v[n] = n;
    for (int i=1;i<=n;++i) w[i] = 0; w[n] = n;
    while (q--) {
        int type, x;
        cin >> type >> x;
        if (type == 1) {
            int got = search(x, rt2, 1, n);
            v[x] = got;
            upd1(x, v[x], rt1, 1, n);
        } else {
            int got = search(x, rt1, 1, n);
            w[x] = got;
            upd1(x, w[x], rt2, 1, n);
        }
    }
    // for (int i=1;i<=n;++i) cout << v[i] << " ";
    // cout << '\n';
    // for (int i=1;i<=n;++i) cout << w[i] << " ";
    // cout << '\n';
    sz = 0;
    SegTree<int> stree(1, n, [](int a, int b) {
        return a + b;
    }, [](int x) {
        return 1;
    });
    LL ans = (n - 2) * 1LL * (n - 2);
    vector<array<int,2>> add;
    for (int i=2;i<n;++i) {
        if (v[i] > 0) {
            ans -= min(n-2, v[i]-1);
        }
        add.push_back({v[i], i});
    }
    // cout << ans << '\n';
    sort(add.begin(), add.end());
    int addsz = add.size(), j = addsz-1;
    for (int i=n-1;i>1;--i) {
        int l = 2, r = min(n-1, w[i]);
        if (l > r) continue;
        while (j >= 0 && add[j][0] >= i) {
            stree.Point_Update(add[j][1], 0);
            // v[add[j][1]] = 0;
            --j;
        }
        if (l <= r) {
            // for (int j=l;j<=r;++j) --ans;
            ans -= stree.Range_Query(l, r);
        }
    }
    // cout << j << " j\n";
    cout << ans << '\n';
}


int vb[N], wb[N];
void brute() {
    cin >> n;
    for (int i=0;i<=n;++i) vb[i] = wb[i] = 0;
    vb[n] = wb[n] = n;
    int q;
    cin >> q;
    while(q--) {
        int type, x;
        cin >> type >> x;
        if (type == 1) {
            for (int j=1;j<=n;++j) if (wb[j] >= x) {
                vb[x] = j;
                break;
            }
        } else {
            for (int j=1;j<=n;++j) if (vb[j] >= x) {
                wb[x] = j;
                break;
            }
        }
    }
    LL ans = (n - 2) * 1LL * (n - 2);
    for (int i=2;i<n;++i) {
        ans -= max(0, min(n-2, vb[i]-1));
    }
    cout << ans << '\n';
    for (int i=2;i<n;++i) {
        int l = 2, r = min(n-1, wb[i]);
        if (l > r) continue;
        int subme = 0;
        for (int j=l;j<=r;++j) if (vb[j] < i) ++subme;
        ans -= subme;
        cout << l << " " << r << " ";
        cout << i << " " << subme << '\n';
    }
    cout << ans << '\n';
}

int main() {
    FASTIO;
    int T = 1;
    // cin >> T;
    while (T--) {
        solve();
        // brute();
    }
    return 0;
} 

Measured memory_bytes: 22088