//Author - Rahil Malhotra
#include "bits/stdc++.h"
using namespace std;
 
template <typename T> void print(T t) { cout<<t<<endl; }
template<typename T, typename... Args> void print(T t, Args... args) { cout<<t<<" "; print(args...); }
 
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl '\n'
#define int long long
#define double long double

int n;
int tree1[1000005],tree2[1000005];
int lazy1[1000005],lazy2[1000005];
void propogate1(int i,int l,int r)
{
    tree1[i]=min(tree1[i],lazy1[i]);
    if(l!=r)
    {
        if(lazy1[i*2]==0)
            lazy1[i*2]=lazy1[i];
        else
            lazy1[i*2]=min(lazy1[i*2],lazy1[i]);
        if(lazy1[i*2+1]==0)
            lazy1[i*2+1]=lazy1[i];
        else
            lazy1[i*2+1]=min(lazy1[i*2+1],lazy1[i]);
    }
    lazy1[i]=0;
}
void propogate2(int i,int l,int r)
{
    tree2[i]=min(tree2[i],lazy2[i]);
    if(l!=r)
    {
        if(lazy2[i*2]==0)
            lazy2[i*2]=lazy2[i];
        else
            lazy2[i*2]=min(lazy2[i*2],lazy2[i]);
        if(lazy2[i*2+1]==0)
            lazy2[i*2+1]=lazy2[i];
        else
            lazy2[i*2+1]=min(lazy2[i*2+1],lazy2[i]);
    }
    lazy2[i]=0;
}
void build(int i,int l,int r)
{
    if(l==r)
    {
        tree1[i]=n;
        tree2[i]=n;
        return;
    }
    int mid=(l+r)/2;
    build(i*2,l,mid);
    build(i*2+1,mid+1,r);
    tree1[i]=min(tree1[i*2],tree1[i*2+1]);
    tree2[i]=min(tree2[i*2],tree2[i*2+1]);
}
void update1(int i,int l,int r,int l1,int r1,int val)
{
    if(lazy1[i])
        propogate1(i,l,r);
    if(l1>r1 || l>r1 || l1>r)
        return;
    if(l1<=l && r<=r1)
    {
        tree1[i]=min(tree1[i],val);
        if(l!=r)
        {
            if(lazy1[i*2]==0)
                lazy1[i*2]=val;
            else
                lazy1[i*2]=min(lazy1[i*2],val);
            if(lazy1[i*2+1]==0)
                lazy1[i*2+1]=val;
            else
                lazy1[i*2+1]=min(lazy1[i*2+1],val);
        }
        return;
    }
    int mid=(l+r)/2;
    update1(i*2,l,mid,l1,r1,val);
    update1(i*2+1,mid+1,r,l1,r1,val);
    tree1[i]=min(tree1[i*2],tree1[i*2+1]);
}
void update2(int i,int l,int r,int l1,int r1,int val)
{
    if(lazy2[i])
        propogate2(i,l,r);
    if(l1>r1 || l>r1 || l1>r)
        return;
    if(l1<=l && r<=r1)
    {
        tree2[i]=min(tree2[i],val);
        if(l!=r)
        {
            if(lazy2[i*2]==0)
                lazy2[i*2]=val;
            else
                lazy2[i*2]=min(lazy2[i*2],val);
            if(lazy2[i*2+1]==0)
                lazy2[i*2+1]=val;
            else
                lazy2[i*2+1]=min(lazy2[i*2+1],val);
        }
        return;
    }
    int mid=(l+r)/2;
    update2(i*2,l,mid,l1,r1,val);
    update2(i*2+1,mid+1,r,l1,r1,val);
    tree2[i]=min(tree2[i*2],tree2[i*2+1]);
}
int query1(int i,int l,int r,int l1,int r1)
{
    if(l1>r1 || l>r1 || l1>r)
        return n;
    if(lazy1[i])
        propogate1(i,l,r);
    if(l1<=l && r<=r1)
        return tree1[i];
    int mid=(l+r)/2;
    return min(query1(i*2,l,mid,l1,r1),query1(i*2+1,mid+1,r,l1,r1));
}
int query2(int i,int l,int r,int l1,int r1)
{
    if(l1>r1 || l>r1 || l1>r)
        return n;
    if(lazy2[i])
        propogate2(i,l,r);
    if(l1<=l && r<=r1)
        return tree2[i];
    int mid=(l+r)/2;
    return min(query2(i*2,l,mid,l1,r1),query2(i*2+1,mid+1,r,l1,r1));
}
int32_t main()
{
    IOS;
    cin>>n;
    build(1,1,n);
    int q;
    cin>>q;
    int totstones=(n-2)*(n-2);
    while(q--)
    {
        int t,x;
        cin>>t>>x;
        if(t==1)
        {
            int minival=query1(1,1,n,x,x);
            //print(t,x,minival);
            totstones-=(minival-2);
            //update in min2 from 2 to minival
            update2(1,1,n,2,minival,x);
        }
        else
        {
            int minival=query2(1,1,n,x,x);
            //print(t,x,minival);
            totstones-=(minival-2);
            //update in min1 from 2 to minival
            update1(1,1,n,2,minival,x);
        }
        //print(totstones);
    }
    print(totstones);
}   


Measured memory_bytes: 19112