#include<bits/stdc++.h>

#ifndef LOCAL
#pragma GCC optimize("O3")
#endif
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma GCC optimize("unroll-loops")

#define endl        '\n'
#define ll          long long
#define pb          push_back
#define vi          vector<ll int>
#define all(a)      (a).begin(),(a).end()
#define F           first
#define S           second
#define rs(v,n)     v.resize(n)
#define hell        1000000007
#define peak        9123372036854775807
#define pii         acos(-1)
#define clr(a,x)    memset(a,x,sizeof(a))
using namespace std;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template<typename T>
using ordered_set = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;

namespace InOp{
template<class x,class y>
istream &operator>>(istream &in,pair<x,y> &p) 
{ 
    in>>p.F>>p.S;
    return in;
}
template<class x>
istream &operator>>(istream &in,vector<x> &v) 
{
    for(auto& i:v)
        in>>i;
    return in;
}
template<class x,class y>
ostream &operator<<(ostream &out,pair<x,y> &p) 
{ 
    out<<"("<<p.F<<","<<p.S<<") ";
    return out; 
}
template<class x>
ostream &operator<<(ostream &out,vector<x> &v) 
{ 
    out<<v.size()<<endl;
    for(auto i:v)
        out<<i<<" ";
    out<<endl;
    return out; 
}
}
using namespace InOp;

namespace ModOp{
template<class x,class y,class z> z add(x a,y b,z m){return (a+b)%m;}
template<class x,class y,class z> z sub(x a,y b,z m){return (a-b+m)%m;}
template<class x,class y,class z> z mul(x a,y b,z m){return ((ll)a*b)%m;}
template<class y,class z> z expo(ll b,y e,z m){ll a=1;b%=m;while(e!=0){if((e&1)==1){a=a*b;a=a%m;}b=b*b;b%=m;e>>=1;}return a%m;}
template<class x,class z> z inv(x b,z m){return expo(b,m-2,m);}
template<class x,class y> x invGeneral(x a,y b){if(a==0)return b==1?0:-1;x m=invGeneral(b%a,a);return m==-1?-1:((1-(ll)b*m)/a+b)%b;}
template<class x,class y,class z> z div(x a,y b,z m){ll c=inv(b,m);return mul(a,c,m);}
}
using namespace ModOp;

namespace Debug{
template<class x> void deb(x a){cerr<<"a"<<": "<<a<<endl;}
template<class x,class y> void deb(x a,y b){cerr<<"a"<<": "<<a<<" | "<<"b"<<": "<<b<<endl;}
template<class x,class y,class z> void deb(x a,y b,z c){cerr<<"a"<<": "<<a<<" | "<<"b"<<": "<<b<<" | "<<"c"<<": "<<c<<endl;}
template<class x,class y,class z,class xy> void deb(x a,y b,z c,xy d){cerr<<"a"<<": "<<a<<" | "<<"b"<<": "<<b<<" | "<<"c"<<": "<<c<<" | "<<"d"<<": "<<d<<endl;}
}
using namespace Debug;

#define N  200005
ll n,l,r;
vi a1(N),seg1(4*N);
void build1(ll cur,ll st,ll end)
{
    if(st==end)
    {
        seg1[cur]=a1[st];
        return;
    }
    ll mid=(st+end)>>1;
    build1(2*cur,st,mid);
    build1(2*cur+1,mid+1,end);
    seg1[cur]=min(seg1[2*cur],seg1[2*cur+1]);    /*  1-change here  */
}
ll query1(ll cur,ll st,ll end,ll l,ll r)
{
    if(l<=st&&r>=end)
    return seg1[cur];
    if(r<st||l>end)
    return hell;                           /*  2-change here  */
    ll mid=(st+end)>>1;
    ll ans1=query1(2*cur,st,mid,l,r);
    ll ans2=query1(2*cur+1,mid+1,end,l,r);
    return min(ans1,ans2);                 /*  3-change here  */
}
void update1(ll cur,ll st,ll end,ll pos,ll upd)
{
    if(st==end)
    {
        a1[pos]=upd;                    /*  4-change here  */
        seg1[cur]=upd;                    /*  5-change here  */
        return;
    }
    ll mid=(st+end)>>1;
    if(st<=pos&&pos<=mid)
        update1(2*cur,st,mid,pos,upd);
    else
        update1(2*cur+1,mid+1,end,pos,upd);
    seg1[cur]=min(seg1[2*cur],seg1[2*cur+1]);    /*  6-change here  */
}
vi a(N),seg(4*N);
void build(ll cur,ll st,ll end)
{
    if(st==end)
    {
        seg[cur]=a[st];
        return;
    }
    ll mid=(st+end)>>1;
    build(2*cur,st,mid);
    build(2*cur+1,mid+1,end);
    seg[cur]=min(seg[2*cur],seg[2*cur+1]);    /*  1-change here  */
}
ll query(ll cur,ll st,ll end,ll l,ll r)
{
    if(l<=st&&r>=end)
    return seg[cur];
    if(r<st||l>end)
    return hell;                           /*  2-change here  */
    ll mid=(st+end)>>1;
    ll ans1=query(2*cur,st,mid,l,r);
    ll ans2=query(2*cur+1,mid+1,end,l,r);
    return min(ans1,ans2);                 /*  3-change here  */
}
void update(ll cur,ll st,ll end,ll pos,ll upd)
{
    if(st==end)
    {
        a[pos]=upd;                    /*  4-change here  */
        seg[cur]=upd;                    /*  5-change here  */
        return;
    }
    ll mid=(st+end)>>1;
    if(st<=pos&&pos<=mid)
        update(2*cur,st,mid,pos,upd);
    else
        update(2*cur+1,mid+1,end,pos,upd);
    seg[cur]=min(seg[2*cur],seg[2*cur+1]);    /*  6-change here  */
}
int main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    ll tt=1;
    // cin>>tt;
    while(tt--)
    {
        ll i,j,k,l,r,x,y,m,n;
        ll q;
        cin>>n>>q;
        for(i=0;i<=n;i++)
        {
            a[i]=n;
            a1[i]=n;
        }
        vi vis(n+1,0),vis1(n+1,0);
        build(1,0,n);
        build1(1,0,n);
        ll ans=(n-2)*(n-2);
        while(q--)
        {
            ll ch;
            cin>>ch>>x;
            if(ch==1)
            {
                if(vis[x]==1)continue;
                y=query(1,0,n,x,n)-1;
                // deb(ch,x,y);
                ans-=y-1;
                ll y1=query1(1,0,n,y,y);
                update1(1,0,n,y,min(x,y1));
            }
            else
            {
                if(vis1[x]==1)continue;
                y=query1(1,0,n,x,n)-1;
                // deb(ch,x,y);
                ans-=y-1;
                ll y1=query(1,0,n,y,y);
                update(1,0,n,y,min(x,y1));
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}

Measured memory_bytes: 21892