class LazyPropSegmentTree:
    def __init__(self, a):
        self.padding = float('inf')        
        self.n = len(a)
        self.N = 1 << (self.n-1).bit_length()
        self.seg_data = [self.padding]*(self.N-1) + a + [self.padding]*(self.N-self.n)
        self.lazy = [self.padding] * (2*self.N - 1)
        for i in range(2*self.N-2, 0, -2):
            self.seg_data[(i-1)>>1] = min(self.seg_data[i], self.seg_data[i-1])
    
    def __len__(self):
        return self.n
    
    def indices_generator(self, i, j):
        # [i, j)
        # [idx1, idx2)を部分的に含むインデックスを降順にyieldするジェネレータ
        idx1 = self.N + i
        idx2 = self.N + j
        lm = (idx1 // (idx1 & -idx1)) >> 1
        rm = (idx2 // (idx2 & -idx2)) >> 1
        while 0 < idx1 < idx2:
            if idx2 <= rm:
                yield idx2-1
            if idx1 <= lm:
                yield idx1-1
            idx1 >>= 1
            idx2 >>= 1
        while idx1:
            yield idx1-1
            idx1 >>= 1
    
    def propagate_down(self, indices):
        # 遅延させていた値を伝搬させる
        # indicesは昇順
        for idx in indices:
            v = self.lazy[idx]
            if v < self.padding:
                idx1, idx2 = 2*idx + 1, 2*idx + 2
                self.lazy[idx1] = min(self.lazy[idx1], v)
                self.lazy[idx2] = min(self.lazy[idx2], v)                
                self.seg_data[idx1] = min(self.seg_data[idx1], v)
                self.seg_data[idx2] = min(self.seg_data[idx2], v)
                self.lazy[idx] = self.padding
    
    def propagate_up(self, indices):
        for idx in indices:
            idx1, idx2 = 2*idx + 1, 2*idx + 2
            self.seg_data[idx] = min(self.seg_data[idx1], self.seg_data[idx2])
    
    def propagate_all(self):
        indices = [i for i in range(self.N-1)]
        self.propagate_down(indices)
        self.propagate_up(indices[::-1])
    
    def update(self, i, j, x):
        *should_prop, = self.indices_generator(i, j)
        self.propagate_down(should_prop[::-1])
        idx1 = self.N - 1 + i
        idx2 = self.N - 2 + j
        while idx1 < idx2 + 1:
            if idx1&1 == 0: # idx1が偶数
                self.seg_data[idx1] = min(x, self.seg_data[idx1])
                self.lazy[idx1] = min(x, self.lazy[idx1])
            if idx2&1 == 1: # idx2が奇数
                self.seg_data[idx2] = min(x, self.seg_data[idx2])
                self.lazy[idx2] = min(x, self.lazy[idx2])
            idx1 >>= 1
            idx2 >>= 1
            idx2 -= 1
        self.propagate_up(should_prop)
    
    def query(self, i, j):
        # [i, j)
        *should_prop, = self.indices_generator(i, j)
        self.propagate_down(should_prop[::-1])
        idx1 = self.N - 1 + i
        idx2 = self.N - 2 + j
        result = self.padding
        while idx1 < idx2 + 1:
                if idx1&1 == 0: # idx1が偶数
                    result = min(result, self.seg_data[idx1])
                if idx2&1 == 1: # idx2が奇数
                    result = min(result, self.seg_data[idx2])                
                idx1 >>= 1
                idx2 >>= 1
                idx2 -= 1
        return result
    

N, Q = map(int, input().split())
query = [tuple(map(int, input().split())) for i in range(Q)]
row = LazyPropSegmentTree([N]*(N+1))
column = LazyPropSegmentTree([N]*(N+1))

ans = (N-2) ** 2
for t, x in query:
    if t == 1:
        n = row.query(x, x+1)
        # print(n)
        ans -= n - 2
        column.update(2, n+1, x)
    else:
        n = column.query(x, x+1)
        # print(n)
        ans -= n - 2
        row.update(2, n+1, x)

print(ans)

Measured memory_bytes: 149356