There is a grid with N rows and N columns of squares. Let (i, j) be the square at the i-th row from the top and the j-th column from the left.
Each of the central (N-2) \times (N-2) squares in the grid has a black stone on it.
Each of the 2N - 1 squares on the bottom side and the right side has a white stone on it.
Q queries are given. We ask you to process them in order.
There are two kinds of queries. Their input format and description are as follows:
 - 1 x: Place a white stone on (1, x). After that, for each black stone between (1, x) and the first white stone you hit if you go down from (1, x), replace it with a white stone.
 - 2 x: Place a white stone on (x, 1). After that, for each black stone between (x, 1) and the first white stone you hit if you go right from (x, 1), replace it with a white stone.
How many black stones are there on the grid after processing all Q queries?

-----Constraints-----
 - 3 \leq N \leq 2\times 10^5
 - 0 \leq Q \leq \min(2N-4,2\times 10^5)
 - 2 \leq x \leq N-1
 - Queries are pairwise distinct.

-----Input-----
Input is given from Standard Input in the following format:
N Q
Query_1
\vdots
Query_Q

-----Output-----
Print how many black stones there are on the grid after processing all Q queries.

-----Sample Input-----
5 5
1 3
2 3
1 4
2 2
1 2

-----Sample Output-----
1

After each query, the grid changes in the following way:

Difficulty: interview

Starter code:

Solutions:
import sys

def solve():
      input = sys.stdin.readline
      N, Q = map(int, input().split())
      total = (N - 2) ** 2
      rb = N
      db = N
      D = [N] * (N + 1)
      R = [N] * (N + 1)
      for _ in range(Q):
            a, b = map(int, input().split())
            if a == 1: #横向き
                  if b < db:
                        total -= (rb - 2)
                        for i in range(b, db): R[i] = rb
                        db = b
                  else:
                        total -= (R[b] - 2)
            else: #縦向き
                  if b < rb:
                        total -= (db - 2)
                        for i in range(b, rb): D[i] = db
                        rb = b
                  else:
                        total -= (D[b] - 2)

      print(total)

      return 0

def __starting_point():
      solve() 
__starting_point()

import sys
import math
from collections import defaultdict, deque, Counter
from copy import deepcopy
from bisect import bisect, bisect_right, bisect_left
from heapq import heapify, heappop, heappush
    
input = sys.stdin.readline
def RD(): return input().rstrip()
def F(): return float(input().rstrip())
def I(): return int(input().rstrip())
def MI(): return map(int, input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int, input().split()))
def TI(): return tuple(map(int, input().split()))
def LF(): return list(map(float,input().split()))
def Init(H, W, num): return [[num for i in range(W)] for j in range(H)]

class BIT():
    # 作りたい要素数nで初期化, 1-index
    # 使用するインスタンス変数の初期化
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (n+1)

    #bit_indexにxをO(log(n))で加算する
    def add(self,i,x):
        #if(i<=0 or i>n):return iに0以下の数字は代入しない
        while i <= self.n:
            self.bit[i] += x
            i += (i & -i)
    #bit_1 + bit_2 + …  + bit_n をO(log(n))で求める
    def sum(self,i):
        s = 0
        #iに0以下の数字は代入しない。
        while i > 0:
            s+=self.bit[i]
            i -= (i & -i)
        return s
    
    def rangesum(self,i,k):
        return self.sum(k) - self.sum(i)
    #a_1 + a_2 + … + a_i >= x となるような最小のiを求める(a_k >= 0)
    #xが0以下の場合は該当するものなし→0を返す
    def lower_bound(self,x):
        if x <= 0:
            return 0
        else:
            i = 0
            r = 1
            #最大としてありうる区間の長さを取得する
            #n以下の最小の二乗のべき(BITで管理する数列の区間で最大のもの)を求める
            while(r<self.n):
                r=r<<1
            len = r
            while len > 0:
                if(i+len<self.n and self.bit[i+len]<x):
                    x-=self.bit[i+len]
                    i+=len
                len = len >> 1
            return i+1

def main():
    N, Q = MI()
    X, Y = BIT(N), BIT(N)
    xmin = N-2
    ymin = N-2
    X.add(1, N-2)
    X.add(N-1, -(N-2))
    Y.add(1, N-2)
    Y.add(N-1, -(N-2))

    res = (N-2)**2
    for i in range(Q):
        a, b = MI()
        if a == 1:
            x = X.sum(b-1)
            if ymin > b-2:
                temp = Y.sum(1)
                Y.add(1, b-2-temp)
                Y.add(xmin+1, -(b-2-temp))
                ymin = b-2
            res -= x
        else:
            y = Y.sum(b-1)
            if xmin > b-2:
                temp = X.sum(1)
                X.add(1, b-2-temp)
                X.add(ymin+1, -(b-2-temp))
                xmin = b-2
            res -= y
            
    print(res)
    
def __starting_point():
    main()
__starting_point()

N, Q = list(map(int, input().split()))

area_W = N - 2
area_H = N - 2

walls_H = []
walls_V = []

count = (N - 2) * (N - 2)

# search smallest i ( s <= i < e ) such that f(i) == True
def bisearch_smallest(f, s, e = None):
	if e == None:
		e = s - 1
		s = 0
	else:
		e -= 1
	
	while s < e:
		m = (s + e) // 2
		if f(m):
			e = m
		else:
			s = m + 1
	
	if s == e and f(s):
		return s
	else:
		return -1

for _ in range(Q):
	q, i = input().split()
	i = int(i) - 2
	if q == "1":
		if i < area_W:
			area_W = i
			count -= area_H
			walls_H.append((i, area_H))
		else:
			j = bisearch_smallest(lambda j: walls_H[j][0] < i, 0, len(walls_H))
			count -= walls_H[j][1]
	else:
		if i < area_H:
			area_H = i
			count -= area_W
			walls_V.append((i, area_W))
		else:
			j = bisearch_smallest(lambda j: walls_V[j][0] < i, 0, len(walls_V))
			count -= walls_V[j][1]

#print(area_W, area_H)
print(count)


import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n, q = list(map(int, input().split()))
    query = [list(map(int, input().split())) for _ in range(q)]

    res = (n - 2) * (n - 2)
    R = C = n - 1
    yoko = [n] * (n - 1)
    tate = [n] * (n - 1)
    for x, y in query:
        y -= 1
        if x == 1:
            if y > C:
                res -= tate[y] - 1
            else:
                res -= R - 1
                tate[y] = 0
                for c in range(C - 1, y, -1):
                    tate[c] = R
                C = y
        else:
            if y > R:
                res -= yoko[y] - 1
            else:
                res -= C - 1
                yoko[y] = 0
                for r in range(R - 1, y, -1):
                    yoko[r] = C
                R = y
    print(res)


def __starting_point():
    resolve()

__starting_point()

from bisect import bisect_right

n,q = map(int,input().split())

v_lay = [(-(n-1),n-2)]
h_lay = [(-(n-1),n-2)]

ans = (n-2)*(n-2)
for _ in range(q):
    case,lay_pos = map(int,input().split())
    
    ref_lay = (v_lay if case==1 else h_lay)
    
    index = bisect_right(ref_lay, (-lay_pos,n))
    _, lay = ref_lay[index-1]
    
    ans -= lay

    if index==len(ref_lay):
        ref_lay = (h_lay if case==1 else v_lay)
        laid_pos, num = ref_lay[-1]
        if laid_pos == -(lay+1):
            ref_lay[-1] = (-(lay+1), min(lay_pos-2,num))
        else:
            ref_lay.append((-(lay+1), lay_pos-2))
            
print(ans)

n, q = list(map(int, input().split()))
query = [list(map(int, input().split())) for _ in range(q)]
INF = 10 ** 9

ver = [-1] * (n + 1)
hor = [-1] * (n + 1)
ver[-1] = INF
hor[-1] = INF
ver_base = n - 1
hor_base = n - 1

white = 2 * n - 1
for num, x in query:
    if num == 1:
        if ver[x] == -1:
            white += ver_base
            i = x
            while ver[i] == -1:
                ver[i] = ver_base
                i += 1

        else:
            white += ver[x]

        hor_base = min(hor_base, x - 1)

    else:
        if hor[x] == -1:
            white += hor_base
            i = x
            while hor[i] == -1:
                hor[i] = hor_base
                i += 1

        else:
            white += hor[x]

        ver_base = min(ver_base, x - 1)

stone_sum = (n - 2) * (n - 2) + 2 * n - 1 + q
ans = stone_sum - white
print(ans)


#import sys
#input = sys.stdin.readline
from collections import deque
from bisect import bisect_left

def main():
    N, Q = list(map( int, input().split()))
    Query = [ tuple( map( int, input().split())) for _ in range(Q)]
    LX = 1
    X = deque([N])
    VX = deque([N])
    LY = 1
    Y = deque([N])
    VY = deque([N])
    mx = N
    my = N
    ans = 0
    # ANS = [0]
    for i, x in Query:
        if i == 1:
            if x < my:
                ans += mx-2
                # Y.appendleft(x)
                # VY.appendleft(mx)
                X.appendleft(x)
                VX.appendleft(mx)
                my = x
            else:
                ans += VX[bisect_left(X,x)-1]-2
                # print("x", x, bisect_left(X,x))
                # print(X, VX)
        else:
            if x < mx:
                ans += my-2
                Y.appendleft(x)
                VY.appendleft(my)

                # X.appendleft(x)
                # VX.appendleft(my)
                mx = x
            else:
                ans += VY[bisect_left(Y,x)-1]-2
                # print("y",x, bisect_left(Y,x))
                # print(Y, VY)

        # print(X, VX)
        # print( ans-ANS[-1])
        # ANS.append(ans)
    #     print(i, x, ans)
    # print(X, VX)
    # print(Y,VY)
    print(((N-2)**2-ans))
def __starting_point():
    main()

__starting_point()

from bisect import bisect

N, Q = list(map(int, input().split()))

ans = (N-2)*(N-2)
wx = wy = 0
Ax = []
Ay = []

for _ in range(Q):
    t, p = list(map(int, input().split()))
    p = N-p
    
    if t==1:
        i = bisect(Ax, (p, 0))
        if i==len(Ax):
            Ax.append((p, wy))
            wx = p
            rev = N-2-wy
        else:
            rev = N-2-Ax[i][1]
    else:
        i = bisect(Ay, (p, 0))
        if i==len(Ay):
            Ay.append((p, wx))
            wy = p
            rev = N-2-wx
        else:
            rev = N-2-Ay[i][1]

    ans -= rev

print(ans)


n, q = list(map(int, input().split()))
query = [list(map(int, input().split())) for _ in range(q)]
INF = 10 ** 9

keys = ["verticle", "horizion"]

become_white = {key: [-1] * (n + 1) for key in keys}
for key in keys:
    become_white[key][-1] = INF
base = {key: n - 1 for key in keys}

white = 2 * n - 1
for num, x in query:
    if num == 1:
        i, j = keys
    else:
        j, i = keys

    if become_white[i][x] == -1:
        white += base[i]
        k = x
        while become_white[i][k] == -1:
            become_white[i][k] = base[i]
            k += 1
    else:
        white += become_white[i][x]

    base[j] = min(base[j], x - 1)

stone_sum = (n - 2) * (n - 2) + 2 * n - 1 + q
ans = stone_sum - white
print(ans)


#!/usr/bin/env python3

import sys
input=sys.stdin.readline

n,q=map(int,input().split())
left=n
up=n
ans=(n-2)*(n-2)
fixed_yoko=[0]*(n+1)
fixed_tate=[0]*(n+1)
post_process=[]
for _ in range(q):
    t,x=map(int,input().split())
    if t==1:
        if x>left:
            post_process.append((t,x))
        else:
            fixed_yoko[left]+=-up
            fixed_yoko[x+1]+=up
            ans-=up-2
            left=x
    elif t==2:
        if x>up:
            post_process.append((t,x))
        else:
            fixed_tate[up]+=-left
            fixed_tate[x+1]+=left
            ans-=left-2
            up=x
for i in range(1,n+1):
    fixed_yoko[i]+=fixed_yoko[i-1]
    fixed_tate[i]+=fixed_tate[i-1]
for t,x in post_process:
    if t==1:
        ans-=fixed_yoko[x]-2
    elif t==2:
        ans-=fixed_tate[x]-2
print(ans)

n, q = list(map(int, input().split()))
n -= 2
X = [[n] * n, [n] * n]
H = [n, n]
ans = n**2
for _ in range(q):
    a, b = list(map(int, input().split()))
    a -= 1
    b -= 2
    for i in range(b, H[a]):
        X[a][i] = H[a ^ 1]
    H[a] = min(H[a], b)
    ans -= X[a][b]
print(ans)


def main():
    N, Q = [int(v) for v in input().split()]

    Query = [[int(v)-1 for v in input().split()] for _ in range(Q)]

    rows = [N-1] * (N - 1)
    cols = [N-1] * (N - 1)

    black = (N - 2) * (N - 2)
    min_row = N - 1
    min_col = N - 1

    for ty, x in Query:
        if ty == 0:
            if x < min_col:
                rows[x:min_col] = [min_row] * (min_col - x)
                min_col = x
            black -= rows[x] - 1
        else:
            if x < min_row:
                cols[x:min_row] = [min_col] * (min_row - x)
                min_row = x
            black -= cols[x] - 1

    print(black)

main()

n, q = list(map(int, input().split()))
n -= 2
R, C = [n] * n, [n] * n
h, w = n, n
a = n**2
for _ in range(q):
    t, x = list(map(int, input().split()))
    x -= 2
    if t == 1:
        for i in range(x, h):
            R[i] = w
        h = min(h, x)
        a -= R[x]
    if t == 2:
        for j in range(x, w):
            C[j] = h
        w = min(w, x)
        a -= C[x]
print(a)


def f(i, m, cnt):
    while True:
        if i > n or not cnt[i] == inf:
            return
        cnt[i] = m
        i += 1

n, q = map(int, input().split())
inf = n + 114514
ans = (n - 2) * (n - 2)
cnt1, cnt2 = [inf] * (n + 1), [inf] * (n + 1)
max1, max2 = n - 2, n - 2
for _ in range(q):
    t, x = map(int, input().split())
    if t == 1:
        if cnt1[x] == inf:
            ans -= max2
            max1 = x - 2
            f(x, max2, cnt1)
        else:
            ans -= cnt1[x]
    else:
        if cnt2[x] == inf:
            ans -= max1
            max2 = x - 2
            f(x, max1, cnt2)
        else:
            ans -= cnt2[x]
print(ans)

import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n, q = list(map(int, input().split()))
    query = [list(map(int, input().split())) for _ in range(q)]

    res = (n - 2) * (n - 2)
    R = C = n - 1
    yoko = [n - 1] * (n - 1)
    tate = [n - 1] * (n - 1)
    for x, y in query:
        y -= 1
        if x == 1:
            if y > C:
                res -= tate[y] - 1
            else:
                res -= R - 1
                for c in range(C - 1, y, -1):
                    tate[c] = R
                C = y
            tate[y] = 0
        else:
            if y > R:
                res -= yoko[y] - 1
            else:
                res -= C - 1
                for r in range(R - 1, y, -1):
                    yoko[r] = C
                R = y
            yoko[y] = 0
    print(res)


def __starting_point():
    resolve()

__starting_point()

import numpy as np
def resolve():
    #n=int(input())
    #a,b=map(int,input().split())
    #x=list(map(int,input().split()))
    #a=[list(map(lambda x:int(x)%2,input().split())) for _ in range(h)]
    n,q=map(int,input().split())
    xe=np.array([0] * n)
    ye=np.array([0] * n)
    xemin,yemin=n-1,n-1
    bs=(n-2)**2
    for i in range(q):
      j,x=map(int,input().split())
      if j==1:
        if xemin>=x-1:
          xe[x-1:xemin]=yemin-1
          xemin=x-1
        bs-=xe[x-1]
      else:
        if yemin>=x-1:
          ye[x-1:yemin]=xemin-1
          yemin=x-1
        bs-=ye[x-1]
    print(bs)
      
def __starting_point():
    resolve()
__starting_point()

n,q=map(int,input().split())
ans=(n-2)**2
h=n-2
r=n-2
l_h=[-1]*(n-2)
l_r=[-1]*(n-2)
for _ in range(q):
    a,x=map(int,input().split())
    if a==1:
        if x-1>r:
            ans-=l_r[x-2]
        else:
            r=x-2
            ans-=h
            for i in range(x-1,n-2):
                if l_r[i]==-1:
                    l_r[i]=h
                else:
                    break
    else:
        if x-1>h:
            ans-=l_h[x-2]
        else:
            h=x-2
            ans-=r
            for i in range(x-1,n-2):
                if l_h[i]==-1:
                    l_h[i]=r
                else:
                    break   
print(ans) 

import sys

sys.setrecursionlimit(10**6)
int1 = lambda x: int(x)-1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

class BIT:
    def __init__(self, n):
        self.inf=10**9
        self.n = n + 3
        self.table = [self.inf] * (self.n + 1)

    def update(self, i, x):
        i += 1
        while i <= self.n:
            if x < self.table[i]: self.table[i] = x
            i += i & -i

    def min(self, i):
        i += 1
        res = self.inf
        while i > 0:
            if self.table[i] < res: res = self.table[i]
            i -= i & -i
        return res

inf=10**9
n,q=MI()
ans=(n-2)**2
t=l=n
yo=[]
ta=[]
for i in range(q):
    op,x=MI()
    if op==1:
        ta.append((i,x))
    else:
        yo.append((i,x))

if not ta or not yo:
    ans-=(len(ta)+len(yo))*(n-2)
    print(ans)
    return

def cnt(ia,jb):
    res=0
    bit=BIT(q+5)
    for i,a in ia:bit.update(i,a)
    jb.sort(key=lambda x:x[1])
    now=2
    for j,b in jb:
        cur=bit.min(j)
        if cur==inf:cur=n
        # print(j,b,cur)
        now=max(now,cur)
        res+=now-2
    return res

ans-=cnt(ta,yo)
ans-=cnt(yo,ta)
print(ans)


def bisect_descending(lst, x):
    l, r = -1, len(lst)
    while r - l > 1:
        m = (r + l) // 2
        if lst[m] > x:
            l = m
        else:
            r = m
    return r


N, Q = list(map(int, input().split()))
row, col = [N], [N]
ans = (N - 2) ** 2
for _ in range(Q):
    n, x = list(map(int, input().split()))
    if n == 1:
        # 下方向
        if x < col[-1]:
            col.append(x)
            row.append(row[-1])
        idx = bisect_descending(col, x)
        ans -= row[idx] - 2
    else:
        # 右方向
        if x < row[-1]:
            row.append(x)
            col.append(col[-1])
        idx = bisect_descending(row, x)
        ans -= col[idx] - 2
print(ans)


n,q = map(int,input().split())

ans = (n-2)**2
rm = n
um = n
ruse = [-1]*(n+1)
uuse = [-1]*(n+1)

for _ in range(q):
    a,x = map(int,input().split())
    if a == 1:
        if uuse[x] >= 0:
            ans -= uuse[x]-2
        else:
            dif = um - 2
            ans -= dif
            for i in range(x,n+1):
                if uuse[i] >= 0:
                    break
                uuse[i] = um
            rm = min(rm,x)
    else:
        if ruse[x] >= 0:
            ans -= ruse[x]-2
        else:
            dif = rm - 2
            ans -= dif
            for i in range(x,n+1):
                if ruse[i] >= 0:
                    break
                ruse[i] = rm
            um = min(um,x)
print(ans)

def search(L, x):
    low, high = 0, len(L)-1
    while low < high:
        mid = (low+high)//2
        if L[mid+1] < x < L[mid]:
            return mid
        elif x < L[mid+1]:
            low = mid+1
        else:
            high = mid
    return low

N, Q = map(int, input().split())
query = [list(map(int, input().split())) for _ in range(Q)]
B = [N-1]
Bv = [N-2]
R = [N-1]
Rv = [N-2]
ans = (N-2)**2
for f, x in query:
    x -= 1
    if f == 1:
        a = search(R, x)
        ans -= Rv[a]
        if R[-1] >= x:
            Bv[-1] = x-1
            R.append(x)
            Rv.append(Rv[-1])
    else:
        a = search(B, x)
        ans -= Bv[a]
        if B[-1] >= x:
            Rv[-1] = x-1
            B.append(x)
            Bv.append(Bv[-1])
    
print(ans)

N, Q = map(int,input().split())
HW = [N, N]
ans = (N - 2) ** 2
L_HW = [[N - 2 for i in range(N)] for j in range(2)]
for _ in range(Q):
    vh, x = map(int,input().split())
    vh -= 1
    if x > HW[1 - vh]:
        ans -= L_HW[1 - vh][x]
    else:
        L_HW[1 - vh][x+1:HW[1 - vh]] = [HW[vh]-2] * (HW[1 - vh]-x-1)
        HW[1 - vh] = x
        ans -= HW[vh] - 2
print(ans)

n, q = map(int, input().split())
l = [0]*n; u = [0]*n; lmin = n-2; umin = n-2; lgoal = n; ugoal = n
for _ in range(q):
    s, t = map(int, input().split())
    if s == 1:
        if t > ugoal: u[t-1] = 0
        else:
            for i in range(t, ugoal-1):u[i] = umin
            lmin = t-2; ugoal = t
    else:
        if t > lgoal: l[t-1] = 0
        else:
            for i in range(t, lgoal-1):l[i] = lmin
            umin = t-2; lgoal = t
print(sum(l)+sum(u)+lmin*umin)

import sys
import numpy as np


def main():
    N, Q = list(map(int, sys.stdin.readline().rstrip().split()))

    H = np.array([0] * (N - 1))
    W = np.array([0] * (N - 1))

    black = (N - 2)**2  # 初期状態の黒枚数

    Hmin = N - 1
    Wmin = N - 1

    for i in range(Q):
        n, x = list(map(int, sys.stdin.readline().rstrip().split()))
        if n == 1:  # ↓ で挟む
            if x - 1 <= Wmin:
                W[x - 1:Wmin] = Hmin - 1
                Wmin = x - 1
            # print("***", W[x - 1], Wmin, Hmin)
            black -= W[x - 1]
        else:
            if x - 1 <= Hmin:
                H[x - 1:Hmin] = Wmin - 1
                Hmin = x - 1
            # print("***", H[x - 1], Wmin, Hmin)
            black -= H[x - 1]

    print(black)


main()


n, q = list(map(int, input().split()))
n -= 2
R, C = [None] * n, [None] * n
h, w = n, n
a = n**2
for _ in range(q):
    t, x = list(map(int, input().split()))
    x -= 2
    if t == 1:
        for i in range(x, h):
            R[i] = w
        h = min(h, x)
        a -= R[x]
    if t == 2:
        for j in range(x, w):
            C[j] = h
        w = min(w, x)
        a -= C[x]
print(a)


n, q = list(map(int, input().split()))
ans = (n-2)**2

d = [n]*(n+1)
r = [n]*(n+1)

rmin = n
dmin = n

for _ in range(q):
    query, x = list(map(int, input().split()))
    if query == 1:
        if x < rmin:
            for i in range(rmin, x-1, -1):
                r[i] = dmin
            rmin = x
        ans -= r[x] - 2

    else:
        if x < dmin:
            for i in range(dmin, x-1, -1):
                d[i] = rmin
            dmin = x
        ans -= d[x] - 2

print(ans)


#!/usr/bin python3
# -*- coding: utf-8 -*-

# Binary Indexed Tree
# 部分和の計算と要素の更新の両方を効率的に行える
# 1-indexed
# sum(r)        :閉区間 [0,r] の合計を取得する
# [8] a0 + a1  + a2 + a3 + a4 + a5 + a6 + a7
# [4] a0 + a1  + a2 + a3
# [2] a0 + a1               [6] a4 + a5
# [1] a0       [3] a2       [5] a4        [7] a6

#                   [1000]
#           [0100]
#   [0010]                [0110]
# [0001]    [0011]      [0111]      [1111]

class BinaryIndexedTree:
    # 初期化処理
    def __init__(self, size):
        self.size = size
        self.dat = [0]*(size+1)
        self.depth = size.bit_length()

    def init(self, a):
        for i, x in enumerate(a):
            self.add(i, x)

    def add(self, i, x):
        i += 1
        while i <= self.size:
            self.dat[i] += x
            i += i & -i # 更新すべき位置

    # sum(r)        :閉区間 [0,r] の合計を取得する
    # sum(0)=a[0], sum(n-1)=a[0]+...+a[n-1]
    def sum(self, r):
        r += 1
        ret = 0
        while r>0:
            ret += self.dat[r]
            r -= r & -r # 加算すべき位置
        return ret

# sum(i) >= vとなる最小のindex
    def lower_bound(self, x):
        """ 累積和がx以上になる最小のindexと、その直前までの累積和 """
        sum_ = 0
        pos = 0
        for i in range(self.depth, -1, -1):
            k = pos + (1 << i)
            if k <= self.size and sum_ + self.dat[k] < x:
                sum_ += self.dat[k]
                pos += 1 << i
        return pos  #0-indexed

#### for debug
    def get_original_sequence(self):
        ret = self.get_aggrigate_sequence()
        for i in range(self.size-1, 0, -1):
            ret[i] -= ret[i-1]
        return ret

    def get_aggrigate_sequence(self):
        return [self.sum(i) for i in range(self.size)]

    def __str__(self):
        seq = self.get_original_sequence()
        ret = 'original :' + ' '.join(map(str, seq))
        ret += '\n'
        seq = self.get_aggrigate_sequence()
        ret += 'aggrigate:' + ' '.join(map(str, seq))
        return ret

########################################
n, q = list(map(int, input().split()))
cx = BinaryIndexedTree(n+1)
cy = BinaryIndexedTree(n+1)
cx.add(1, n-2)
cy.add(1, n-2)
mx, my = n, n
ret = pow(n-2,2)
for _ in range(q):
    u, v = list(map(int, input().split()))
    if u == 1:
        ret -= cx.sum(v)
        if mx > v:
            cy.add(1, v-mx)
            cy.add(my, mx-v)
            mx = v
    else:
        ret -= cy.sum(v)
        if my > v:
            cx.add(1, v-my)
            cx.add(mx, my-v)
            my = v

print(ret)


n, q = map(int, input().split())
queries = [list(map(int, input().split())) for _ in range(q)]

v = n-1 # 最も上にある白石のy座標
h = n-1 # 最も左にある白石のx座標
tate = [n-1] * n
yoko = [n-1] * n
ans = (n-2)**2
for q1, q2 in queries:
    q2 -= 1
    if q1 == 1:
        # タテの処理
        if q2 < h:
            ans -= v-1
            # 左上の矩形より外は、更新されることがなくなったらtate yokoに格納
            # それぞれの更新は高々n回
            for i in range(h, q2, -1):
                tate[i] = v
            h = q2
        else:
            ans -= tate[q2]-1
    else:
        #  ヨコの処理
        if q2 < v:
            ans -= max(0, h-1)
            for i in range(v, q2, -1):
                yoko[i] = h
            v = q2
        else:
            ans -= yoko[q2]-1
print(ans)

class F:
    def __init__(self, x):
        self.bit = x
        for i in range(len(x)):
            j = i | (i + 1)
            if j < len(x):
                x[j] += x[i]
    def update(self, idx, x):
        while idx < len(self.bit):
            self.bit[idx] += x
            idx |= idx + 1
    def query(self, end):
        x = 0
        while end:
            x += self.bit[end - 1]
            end &= end - 1
        return x
    def findkth(self, k):
        idx = -1
        for d in reversed(range(len(self.bit).bit_length())):
            right_idx = idx + (1 << d)
            if right_idx < len(self.bit) and k >= self.bit[right_idx]:
                idx = right_idx
                k -= self.bit[idx]
        return idx + 1
import sys
z=sys.stdin.readline
y=lambda:map(int,z().split())
n,q=y()
v=F([0]*(n-2))
h=F([0]*(n-2))
w=j=n-2
s=0
for _ in range(q):
    a,b=y()
    if a<2:
        if b-2<w:h.update(n-2-j,w-b+2);w=b-2
        s+=n-2-v.query(n-b)
    else:
        if b-2<j:v.update(n-2-w,j-b+2);j=b-2
        s+=n-2-h.query(n-b)
print((n-2)*(n-2)-s)

import sys
input=sys.stdin.readline
def main():
    n, q=list(map(int,input().split()))
    ans = (n-2)**2
    h = n
    w = n
    a=[n for _ in range(n)]
    b=[n for _ in range(n)]
    for _ in range(q):
        t, x=list(map(int,input().split()))
        if (t == 1):
            if (x < w):
                for i in range(x,w):
                    a[i] = h
                w = x
            ans -= a[x] - 2
        else:
            if (x < h):
                for i in range(x,h):
                    b[i] = w
                h = x
            ans -= b[x] - 2
    print(ans)
def __starting_point():
    main()

__starting_point()

N, Q, *QX = map(int, open(0).read().split())

A = [N] * (N + 1)
B = [N] * (N + 1)

ans = (N - 2) ** 2
h = w = N
for q, x in zip(*[iter(QX)] * 2):
    if q == 1:
        if x < w:
            B[x:w] = [h] * (w - x)
            w = x
        ans -= B[x] - 2
    else:
        if x < h:
            A[x:h] = [w] * (h - x)
            h = x
        ans -= A[x] - 2

print(ans)

import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    if len(x) == 0:
        return []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def pow_k(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans

"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""


n,q = m()

ans = (n-2)**2

ta = n-2
tate = [n-2 for i in range(n-2)]
ltate = [0 for i in range(n-2)]
yo = n-2
yoko = [n-2 for i in range(n-2)]
lyoko = [0 for i in range(n-2)]
for i in range(q):
    a,b = m()
    b -= 2
    if a == 1:
        if ltate[b] == 0:
            ans -= ta
        else:
            ans -= tate[b]

        for j in range(b,n-2):
            if ltate[j] == 0:
                tate[j] = ta
                ltate[j] = 1
                yo = b
            else:
                break


    else:
        if lyoko[b] == 0:
            ans -= yo
        else:
            ans -= yoko[b]
        for j in range(b,n-2):
            if lyoko[j] == 0:
                yoko[j] = yo
                lyoko[j] = 1
                ta = b
            else:
                break
print(ans)

N, Q = list(map(int, input().split()))

row = [N - 2] * (N + 2)
col = [N - 2] * (N + 2)
ans = (N - 2)**2

miRow = N
miCol = N

for _ in range(Q):
    q, x = list(map(int, input().split()))

    if q == 1:
        for i in range(x, miRow + 1):
            row[i] = min(row[i], miCol - 2)
        miRow = min(x, miRow)
        ans -= row[x]

    if q == 2:
        for i in range(x, miCol + 1):
            col[i] = min(col[i], miRow - 2)
        miCol = min(x, miCol)
        ans -= col[x]

print(ans)


import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n, q = list(map(int, input().split()))
    query = [list(map(int, input().split())) for _ in range(q)]

    res = (n - 2) * (n - 2)
    Y = n - 1
    T = n - 1
    yoko = [n - 1] * (n - 1)
    tate = [n - 1] * (n - 1)
    for num, x in query:
        x -= 1
        if num == 1:
            if x > Y:
                res -= tate[x] - 1
            else:
                res -= T - 1
                for i in range(x, Y):
                    tate[i] = T
                Y = x
            tate[x] = 0
        else:
            if x > T:
                res -= yoko[x] - 1
            else:
                res -= Y - 1
                for i in range(x, T):
                    yoko[i] = Y
                T = x
            yoko[x] = 0
    print(res)


def __starting_point():
    resolve()

__starting_point()

from collections import deque
from bisect import bisect_left, bisect_right

n, q = map(int, input().split())
list_x = deque()
list_y = deque()
memo_x = deque()
memo_y = deque()
x_now, y_now = n-1, n-1

ans = (n-2) ** 2

#que = [(1, i) for i in range(2, n)] + [(2, i) for i in range(2, n)]
for i in range(q):
    flg, x = map(int, input().split())
    if flg == 1:
        if x_now >= x:
            ans -= y_now - 1
            x_now = x - 1
            list_x.appendleft(x)
            memo_x.appendleft(y_now - 1)
        else:
            tmp = bisect_left(list_x, x) - 1
            ans -= memo_x[tmp]
    
    else:
        y = x
        if y_now >= y:
            ans -= x_now - 1
            y_now = y - 1
            list_y.appendleft(y)
            memo_y.appendleft(x_now - 1)
        else:
            tmp = bisect_left(list_y, y) - 1
            ans -= memo_y[tmp]

print(ans)

n, q = map(int, input().split())
query = [list(map(int, input().split())) for _ in range(q)]

ans = (n-2)**2
x = [n] * (n+1)
y = [n] * (n+1)
xm = ym = n

for a, b in query:
    if a == 1:
        if b < xm:
            y[b:xm] = [ym] * (xm - b)
            xm = b
        ans -= y[b] - 2
    else:
        if b < ym:
            x[b:ym] = [xm] * (ym - b)
            ym = b
        ans -= x[b] - 2
print(ans)

import numpy as np
# from numba import njit
# from numba.types import int64
i8 = np.int64


# @njit((int64, int64[:,::-1]), cache=True)
def solve(n, qr):
    col = np.zeros(n - 1, i8)
    col[0] = 0
    col_min = n - 1
    row = np.zeros(n - 1, i8)
    row[0] = 0
    row_min = n - 1
    white = 0
    for i in range(qr.shape[0]):
        j = qr[i, 1] - 1
        if qr[i, 0] == 1:
            if j < col_min:
                white += row_min - 1
                for m in range(j + 1, col_min):
                    col[m] = row_min - 1
                col_min = j
            else:
                white += col[j]
        else:
            if j < row_min:
                white += col_min - 1
                for m in range(j + 1, row_min):
                    row[m] = col_min - 1
                row_min = j
            else:
                white += row[j]
    return white


def main():
    f = open(0)
    n, q = [int(x) for x in f.readline().split()]
    qr = np.fromstring(f.read(), i8, sep=' ').reshape((-1, 2))
    white = solve(n, qr)
    print((n - 2) ** 2 - white)

main()

import sys
import bisect
input = sys.stdin.readline

def main():
    n, q = list(map(int, input().split()))

    ans = 0
    min1, min2 = n-2, n-2
    judge1 = [-n-1]
    judge2 = [-n-1]
    dict1 = dict()
    dict2 = dict()
    dict1[-n-1] = n-2
    dict2[-n-1] = n-2

    for i in range(q):
        query, x = list(map(int, input().split()))

        if query == 1:
            index = bisect.bisect(judge1, -x)-1
            key = dict1[judge1[index]]
            ans += key
            if min1 > x-2:
                min1 = x-2
                judge1.append(-x)
                dict1[-x] = key
                dict2[judge2[-1]] = min1
        else:
            index = bisect.bisect(judge2, -x)-1
            key = dict2[judge2[index]]
            ans += key
            if min2 > x-2:
                min2 = x-2
                judge2.append(-x)
                dict2[-x] = key
                dict1[judge1[-1]] = min2

    print(((n-2)**2 - ans))
    
    
    
    
def __starting_point():
    main()

__starting_point()

def f_simplified_reversi():
    N, Q = [int(i) for i in input().split()]
    Queries = [[int(i) for i in input().split()] for j in range(Q)]

    a, b = [N] * N, [N] * N  # editorial に準じる
    black_stone = (N - 2)**2
    row, col = N, N

    for type, x in Queries:
        if type == 1:
            if x < col:
                for i in range(x, col):
                    b[i] = row
                col = x
            black_stone -= b[x] - 2
        else:
            if x < row:
                for i in range(x, row):
                    a[i] = col
                row = x
            black_stone -= a[x] - 2
    return black_stone

print(f_simplified_reversi())

def main():
    N, Q = [int(v) for v in input().split()]

    Query = [[int(v)-1 for v in input().split()] for _ in range(Q)]

    rows = [N-1] * (N - 1)
    cols = [N-1] * (N - 1)

    black = (N - 2) * (N - 2)
    min_row = N - 1
    min_col = N - 1

    for ty, x in Query:
        if ty == 0:
            if x < min_col:
                for j in range(x, min_col):
                    rows[j] = min_row
                min_col = x
            black -= rows[x] - 1
        else:
            if x < min_row:
                for j in range(x, min_row):
                    cols[j] = min_col
                min_row = x
            black -= cols[x] - 1

    print(black)

main()

N, Q = list(map(int, input().split()))
Query = [list(map(int, input().split())) for _ in range(Q)]
ans = 0

for T in range(1, 3):
    Depth = [N-2]*N
    left = N
    up = N-2
    for t, x in Query:
        if t == T:  # |
            if left < x:
                ans += Depth[x]
            else:
                for i in range(x, left):
                    Depth[i] = up
                left = x
                ans += up
        else:  # -
            up = min(up, x-2)
        #print(f"ans={ans}, up={up}")
    #print("---")

print(((N-2)**2-ans))


A,B,C,D=lambda:map(int,input().split()),range,min,max
n,q=A()
a,b=[n]*n,[n]*n
h,w=n,n
E=(n-2)**2
for _ in B(q):
 Q,x=A()
 if Q-1:
  for i in B(x,D(x,h)):b[i-1]=w
  h=C(h,x);E-=b[x-1]-2
 else:
  for i in B(x,D(x,w)):a[i-1]=h
  w=C(w,x);E-=a[x-1]-2
print(E)

N,Q = map(int,input().split())
a,b = [N]*(N+1),[N]*(N+1)

H,W = N,N

black = (N-2)**2

for _ in range(Q):
  t,x = map(int,input().split())
  if t == 1:
    if x < W:
      for i in range(x,W):
        b[i] = H
      W = x

    black -= b[x] - 2
  
  else:
    if x < H:
      for i in range(x,H):
        a[i] = W
      H = x

    black -= a[x] - 2
  

print(black)