/**
* Dont raise your voice, improve your argument.
* --Desmond Tutu
*/
#include <bits/stdc++.h>
using namespace std;
const bool ready = [](){
ios_base::sync_with_stdio(false); cin.tie(0);
cout << fixed << setprecision(12);
return true;
}();
const double PI = acos(-1);
using ll= long long;
#define int ll
#define all(v) (v).begin(), (v).end()
#define fori(n) for(int i=0; i<int(n); i++)
#define cini(i) int i; cin>>i;
#define cins(s) string s; cin>>s;
#define cind(d) double d; cin>>d;
#define cinai(a,n) vi a(n); fori(n) { cin>>a[i]; }
#define cinas(s,n) vs s(n); fori(n) { cin>>s[i]; }
#define cinad(a,n) vd a(n); fori(n) { cin>>a[i]; }
using pii= pair<int, int>;
using pdd= pair<double, double>;
using vd= vector<double>;
using vb= vector<bool>;
using vi= vector<int>;
using vvi= vector<vi>;
using vs= vector<string>;
#define endl "\n"
template<typename E>
struct SegmentTreeLazy {
vector<E> data;
vector<E> lazyInc;
vector<bool> lazyIncB; /* flag if there is a pending lazyInc in node */
vector<E> lazySet;
vector<bool> lazySetB; /* flag if there is a pending lazySet in node */
E neutral;
int n;
function<E(E,E)> plus;
function<E(E,int)> mult;
SegmentTreeLazy(int _n, E _neutral) {
n=1;
while(n<_n)
n*=2;
data.resize(n*2, _neutral);
lazyInc.resize(n*2, _neutral);
lazyIncB.resize(n*2);
lazySet.resize(n*2, _neutral);
lazySetB.resize(n*2);
neutral=_neutral;
}
/* bulk update in O(n) */
template<typename Iterator>
void init(Iterator beg, Iterator end) {
for(int idx=n; beg!=end; beg++, idx++)
data[idx]=*beg;
for(int idx=n-1; idx>=1; idx--)
data[idx]=plus(data[idx*2], data[idx*2+1]);
}
/* pushes down the pending updates to the vertex node
* If both lazies are set then the inc was later, so both
* have to be pushed.
* But first the set, which erases all previously set
* and inc on the child nodes, then the inc.
* */
void pushlazy(int node, int sL, int sR) {
if(lazySetB[node]) {
//cerr<<"pushlazy Set, node="<<node<<" sL="<<sL<<" sR="<<sR<<endl;
if(sL!=sR) {
int mid=(sL+sR)/2;
rangeSet(node*2, sL , mid, sL , mid, lazySet[node]);
rangeSet(node*2+1, mid+1, sR , mid+1, sR , lazySet[node]);
}
lazySetB[node]=false;
lazySet[node]=neutral;
}
if(lazyIncB[node]) {
//cerr<<"pushlazy Inc, node="<<node<<" sL="<<sL<<" sR="<<sR<<endl;
if(sL!=sR) {
int mid=(sL+sR)/2;
rangeInc(node*2, sL , mid, sL , mid, lazyInc[node]);
rangeInc(node*2+1, mid+1, sR , mid+1, sR , lazyInc[node]);
}
lazyIncB[node]=false;
lazyInc[node]=neutral;
}
}
/* @return accumulative (l,r), both inclusive, top down */
E query(int node, int sL, int sR, int l, int r) {
if (r < sL || l > sR)
return neutral;
//cerr<<"query, node="<<node<<" sL="<<sL<<" sR="<<sR<<" l="<<l<<" r="<<r<<" data[node]="<<data[node]<<endl;
if (l<=sL && r>=sR)
return data[node];
pushlazy(node, sL, sR);
int mid = (sL+sR)/2;
return plus(query(node*2, sL, mid, l, r), query(node*2+1, mid+1, sR, l, r));
}
E query(int l, int r) {
return query(1, 0, n-1, l, r);
}
/* set all position in (l,r) to val */
void rangeSet(int node, int sL, int sR, int l, int r, E val) {
if (r < sL || l > sR)
return;
//cerr<<"rangeSet node="<<node<<" sL="<<sL<<" sR="<<sR<<" l="<<l<<" r="<<r<<" val="<<val<<endl;
if(l<=sL && r>=sR) {
lazySet[node]=val;
lazyInc[node]=neutral;
lazySetB[node]=true;
lazyIncB[node]=false;
data[node]=mult(val, sR-sL+1);
//cerr<<"rangeSet did set node="<<data[node]<<endl;
return;
}
pushlazy(node, sL, sR);
int mid = (sL+sR)/2;
rangeSet(node*2 , sL , mid, l, r, val);
rangeSet(node*2+1, mid+1, sR , l, r, val);
data[node]=plus(data[node*2], data[node*2+1]);
}
/* set val at positions (l,r) */
void rangeSet(int l, int r, E val) {
rangeSet(1, 0, n-1, l, r, val);
}
/* increment all position in (l,r) by inc */
void rangeInc(int node, int sL, int sR, int l, int r, E inc) {
if (r < sL || l > sR)
return;
//cerr<<"rangeInc node="<<node<<" sL="<<sL<<" sR="<<sR<<" l="<<l<<" r="<<r<<" val="<<inc<<endl;
if(l<=sL && r>=sR) {
lazyInc[node]=plus(lazyInc[node], inc);
lazyIncB[node]=true;
data[node]=plus(data[node], mult(lazyInc[node], sR-sL+1));
//cerr<<"rangeInc did set node="<<data[node]<<endl;
return;
}
pushlazy(node, sL, sR);
int mid = (sL+sR)/2;
rangeInc(node*2 , sL , mid, l, r, inc);
rangeInc(node*2+1, mid+1, sR , l, r, inc);
data[node]=plus(data[node*2], data[node*2+1]);
}
/* increment by inc at positions (l,r) */
void rangeInc(int l, int r, E inc) {
rangeInc(1, 0, n-1, l, r, inc);
}
};
/*
* N*N grid
* We got row and col queryies, which work symetric.
* We need to know forach row what is the leftmost col
* that was turned to white.
*
* let q1 be "1 4", ie new stone at col 4
* we need to find the smallest row move which blocked col 4.
* Since first move there is none.
* So q1 blocks all rows at col 4.
* -> SegmentTree
*
* foreach move count the flipped stones.
*/
const int INF=1e9;
void solve() {
cini(n);
cini(q);
SegmentTreeLazy srow(n+1, INF);
SegmentTreeLazy scol(n+1, INF);
srow.plus=scol.plus=[](int i1, int i2) { return min(i1, i2); };
srow.mult=scol.mult=[](int i1, int i2) { return i1; };
vi data(n+1, n);
srow.init(all(data));
scol.init(all(data));
int ans=(n-2)*(n-2);
for(int i=0; i<q; i++) {
cini(t);
cini(x);
//cerr<<"t="<<t<<" x="<<x<<endl;
if(t==1) { /* place stone at col==x */
int block=scol.query(x,x);
ans-=(block-2);
//cerr<<"block="<<block<<endl;
srow.rangeInc(1, block-1, x);
} else if(t==2) { /* place stone at row==x */
int block=srow.query(x,x);
ans-=(block-2);
//cerr<<"block="<<block<<endl;
scol.rangeInc(1, block-1, x);
} else
assert(false);
}
cout<<ans<<endl;
}
signed main() {
solve();
}
// FIRST THINK, THEN CODE
// DO NOT JUMP BETWEEN PROBLEMS