#include <bits/stdc++.h>
#include <iostream>
#include <ctime>
using namespace std;
#define _LL long long
#define rep(i, n) for (_LL i = 0; i < (_LL)(n); i++)
#define vecrep(itr, v) for (auto itr = (v).begin(); itr != (v).end(); itr++)

template<class T, class U> class SegTreeDelaySkelton
{
    private:
        int _n;
        int _d;
        int _bit;
        T* nodes;
        bool *_used;
        // 子に伝搬する情報があるか
        bool *_last;

        // leftとrightでparentを更新。left, rightにNULLが入ることも。[indexl, indexr)までがparentの担当
        void (*_update)(T* parent, T* left, T* right, int indexl, int indexr);

        // nodeをvで更新する。（親への伝搬はクラス内で処理）
        void (*_rangef)(T* node, T* v, int indexl, int indexr);

        U (*_get)(T* node, U lv, U rv, int l, int r, int indexl, int indexr);

    public:
        SegTreeDelaySkelton(int n, void (*update)(T*, T*, T*, int, int), void (*f)(T*, T*, int, int) )
        {
            construct(n, update, f);
        }

        SegTreeDelaySkelton(int n, void (*update)(T*, T*, T*, int, int), void (*f)(T*, T*, int, int), T def)
        {
            construct(n, update, f);
            for(int i = 0; i < n; i++ ) nodes[_bit + i] = def;
            for(int i = _bit - 1; i >= 0; i-- ) 
                if(_used[i]) callupdate(i);
        }

        void setGet( U (*get)(T*, U, U, int, int, int, int) )
        {
            _get = get;
        }

        void set(int index, T node)
        {
            nodes[_bit + index] = node;
            updatenode((_bit + index) / 2);
        }

        void updatenode(int i)
        {
            callupdate(i);
            if( i > 1) updatenode( i / 2 );
        }

        T* top() { return nodes + 1;}
        U get(int l) { return getRangeSub(l, l + 1, 1); }

        void range(int l, int r, T* v)
        {
            rangeSub(l, r, v, 1);
        }

        U getrange(int l, int r)
        {
            return getRangeSub(l, r, 1);
        }

        ~SegTreeDelaySkelton()
        {
            delete nodes;
            delete _used;
        }
    private:

        T* getnode(int i)
        {
            return _used[i] ? nodes + i : NULL;
        }

        T getsub(int index, int l)
        {
            if( index >= _bit ) return nodes[index];
            int nodel, noder, nodec;
            getindex(index, nodel, noder);
            nodec = (nodel + noder) / 2;             
            if( _last[index] )
            {
                if( _get == NULL ) return nodes[index];
                T ret = getsub(l < nodec ? (index * 2) : (index * 2 + 1), l);
                _get(nodes + index, &ret, l);
                return ret;
            }
            return getsub(l < nodec ? (index * 2) : (index * 2 + 1), l);
        }        

        void callupdate(int i)
        {
            int nodel, noder;
            getindex(i, nodel, noder);

            int t = i; int topd = 1;
            while( t > 1 ) { topd = (topd << 1); t = ( t >> 1);}
            int no = i - topd;
            int k = _bit / topd;            
            _update(nodes + i, getnode(i * 2), getnode(i * 2 + 1), nodel, noder);
        }

        void construct(int n, void (*update)(T*, T*, T*, int, int), void (*f)(T*, T*, int, int))
        {
            _get = NULL;
            _update = update;
            _rangef = f;
            _n = n;
            _d = 1;
            _bit = 1;
            while( _bit < _n )
            {
                _bit *= 2;
                _d++;
            }
            nodes = new T[_bit * 2];
            _used = new bool[_bit * 2];
            _last = new bool[_bit * 2];
            for(int i = 0; i < _bit * 2; i++ ) _last[i] = false;
            for(int i = 0; i < n; i++ ) _used[_bit + i] = true;
            for(int i = _bit - 1; i > 0; i-- ) _used[i] = (_used[i * 2] || _used[i * 2 + 1]);
        }

        void getindex(int i, int &nodel, int &noder)
        {
            int t = i; int topd = 1;
            while( t > 1 ) { topd = (topd << 1); t = ( t >> 1);}
            int no = i - topd;
            int k = _bit / topd;    
            nodel = k * no;
            noder = k * (no + 1);   
        }

        void rangeSub(int l, int r, T *v, int index)
        {
            int nodel, noder, nodec;
            getindex(index, nodel, noder);
            nodec = nodel + (noder - nodel) / 2;
            if( noder - nodel <= 1 || (l <= nodel && r >= noder) ) { _last[index] = true; _rangef(nodes + index, v, nodel, noder); return;}
            // 伝搬
            if(  _last[index] )
            {
                if( _used[index * 2]) { _rangef(nodes + index * 2, nodes + index, nodel, nodec); _last[index * 2] = true; }
                if( _used[index * 2 + 1]) {_rangef(nodes + index * 2 + 1, nodes + index, nodec, noder); _last[index * 2 + 1] = true; }
                nodes[index].reset();
            }
            _last[index] = false;

            if( l < nodec && r > nodel ) rangeSub(l, r, v, index * 2);
            if( r > nodec && l < noder ) rangeSub(l, r, v, index * 2 + 1);
            _update(nodes + index, getnode(index * 2), getnode(index * 2 + 1), nodel, noder);
        }    

        U getRangeSub(int l, int r, int index)
        {
            int nodel, noder, nodec;
            getindex(index, nodel, noder);
            if( r <= nodel || l>= noder ) return U(0);
            nodec = nodel + (noder - nodel) / 2;
            if( noder - nodel <= 1 || (l <= nodel && r >= noder) ) return _get(nodes + index, U(0), U(0), l, r, nodel, noder);
            return _get(nodes + index, getRangeSub(l, r, index * 2), getRangeSub(l, r, index * 2 + 1), l, r, nodel, noder);
        }              
};

struct SumNode
{
    int value;

    SumNode() { value = (1 << 30); }
    void reset()
    {
        value = (1 << 30);
    }
};


void updatesum(SumNode* parent, SumNode* left, SumNode* right, int indexl, int indexr)
{
}

void addrange(SumNode* node, SumNode *v, int indexl, int indexr)
{
    node->value = min(v->value, node->value);
}

int addget(SumNode* node, int lv, int rv, int l, int r, int indexl, int indexr)
{
    // l + 1 == rでしかよばない前提
    if( indexr - indexl == 1 || l <= indexl && r >= indexr  ) return node->value;
    int indexc = (indexl + indexr) / 2;
    if( r <= indexc ) return min(lv, node->value);
    if( l >= indexc ) return min(rv, node->value);
    return min(lv, node->value);
}

void setsub(SegTreeDelaySkelton<SumNode, int> &st, int l, int r, int v)
{
    SumNode tmp;
    tmp.value = v;
    st.range(l, r, &tmp);
}

int main()
{
    _LL n, q; cin >> n >> q;
    _LL sum = 0;
    SegTreeDelaySkelton<SumNode, int> vmin(n, updatesum, addrange);
    SegTreeDelaySkelton<SumNode, int> hmin(n, updatesum, addrange);
    vmin.setGet(addget);
    hmin.setGet(addget);
    setsub(vmin, 0, n, n);
    setsub(hmin, 0, n, n);
    rep(i, q)
    {
        int t, x;
        cin >> t >> x;
        if( t == 1 )
        {
            int wall = hmin.get(x);
            sum += wall - 2;
            setsub(vmin, 1, wall, x);
        }
        else
        {
            int wall = vmin.get(x);
            sum += wall - 2;
            setsub(hmin, 1, wall, x);
        }
    }
    cout << (n - 2) * (n - 2) - sum << endl;
    return 0;    
}

Measured memory_bytes: 9236