#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> iint;
typedef pair<ll,ll> llll;
#define ALL(x) (x).begin(),(x).end()
const ll zero = 0;
const ll one = 1;
const ll INF = 9223372036854775807; //10^18
const int inINF = 2147483647; //10^9
const ll MOD = 1000000007; //10^9+7
const ll MOD2 = 998244353;
void Yes() {printf("Yes\n");}
void No() {printf("No\n");}
void YES() {printf("YES\n");}
void NO() {printf("NO\n");}


//RUQを得るためのセグメント木
struct SegmentTree {
private:
    int n;
    vector<int> node;

public:
    // SegmentTree seg(元となる配列) で宣言する

    // 元配列 v をセグメント木で表現する
    SegmentTree(vector<int> v) {
        // n  = v のサイズ以上の最小の2冪
        // sz = v のサイズ

        // セグメント木全体で必要なノード数は 2n-1 個である
        int sz = v.size();
        n = 1; while(n < sz) n *= 2;

        //////////////////////////////////////////
        // セグメント木の初期化
        // 初期化の値は機能によって変える
        node.resize(2*n-1, 0);

        //////////////////////////////////////////
        // 最下段より上にはn-1個のノードがある
        // 最下段のインデックスはn-1からn-1 + sz-1まで
        // 最下段に値を入れたあとに、下の段から順番に値を入れる
        // 値を入れるには、自分の子の 2 値を参照すれば良い
        for(int i=0; i<sz; i++) node[i+n-1] = v[i];
        for(int i=n-2; i>=0; i--) node[i] = max(node[2*i+1], node[2*i+2]);
    }

    // インデックスxの値を返す
    int get(int x) {
        // 最下段のノードにアクセスする
        x += (n - 1);

        //////////////////////////////////////////
        // 最下段のノードを更新したら、あとは親に上って更新していく
        int ret = node[x];
        while(x > 0) {
            x = (x - 1) / 2;
            ret = max(ret, node[x]);
        }
        return ret;
    }

    // xより大きい最小のindexを返す
    int bin(int x){
        int ok = n;
        int ng = -1;
        while(ng + 1 < ok){
            int mid = (ok + ng) / 2;
            if(f(mid, x)){
                ok = mid;
            }
            else{
                ng = mid;
            }
        }
        return ok;
    }

    bool f(int i, int x){
        return get(i) > x;
    }

    // 要求区間 [a, b) 中の要素の最小値を答える
    // k := 自分がいるノードのインデックス
    // 対象区間は [l, r) にあたる

    // [a, b)をiに更新する。今考えている区間は[l, r)
    void update(int a, int b, int i, int k=0, int l=0, int r=-1) {
        // まずは区間[0, n)を考える
        if(r < 0) r = n;

        //////////////////////////////////////////
        // 考えている区間と[a, b)が交わらない -> 適当に返す
        if(r <= a || b <= l) return;

        //////////////////////////////////////////
        // [a, b)が考えている区間を完全に被覆 -> 考えている区間を答えの計算に使う
        if(a <= l && r <= b) {
            node[k] = i;
            return;
        }

        //////////////////////////////////////////
        // [a, b)が考えている区間の一部を被覆 -> 子について探索を行う
        // 左側の子を vl ・ 右側の子を vr としている
        // 新しく考える区間は、現在考えている区間を半分に割ったもの
        update(a, b, i, 2*k+1, l, (l+r)/2);
        update(a, b, i, 2*k+2, (l+r)/2, r);
        return;
    }
};


int main(){
    int N, Q;
    cin >> N >> Q;
    ll w = 0;
    int q, x;
    
    vector<int> X, Y;
    vector<int> v(N, 0);
    SegmentTree mx(v);
    SegmentTree my(v);
    X.push_back(N-2);
    Y.push_back(N-2);
    int indx = 1;
    int indy = 1;

    for (int i = 0; i < Q; i++) {
        cin >> q >> x; x -= 2;
        if(q == 1){
            int ok = N;
            int ng = -1;
            while(ng + 1 < ok){
                int mid = (ok + ng) / 2;
                if(X[mx.get(mid)] > x){
                    ok = mid;
                }
                else{
                    ng = mid;
                }
            }
            int ind = ok;
            int ine = Y[my.get(x)];
            w = w + ine;
            if(ine - 1 >= ind){
                mx.update(ind, ine, indx);
                X.push_back(x);
                indx++;
            }
        }
        else{
            int ok = N;
            int ng = -1;
            while(ng + 1 < ok){
                int mid = (ok + ng) / 2;
                if(Y[my.get(mid)] > x){
                    ok = mid;
                }
                else{
                    ng = mid;
                }
            }
            int ind = ok;
            int ine = X[mx.get(x)];
            w = w + ine;
            if(ine - 1 >= ind){
                my.update(ind, ine, indy);
                Y.push_back(x);
                indy++;
            }            
        }
    }
    ll NN = N;
    ll ans = (NN-2) * (NN-2);
    ans -= w;
    printf("%lld\n", ans);

}

Measured memory_bytes: 9292