Home


Contest: Task: Related: TaskE TaskG

Score : $600$ points

Problem Statement

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 1

5 5
1 3
2 3
1 4
2 2
1 2

Sample Output 1

1

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

Figure


Sample Input 2

200000 0

Sample Output 2

39999200004

Sample Input 3

176527 15
1 81279
2 22308
2 133061
1 80744
2 44603
1 170938
2 139754
2 15220
1 172794
1 159290
2 156968
1 56426
2 77429
1 97459
2 71282

Sample Output 3

31159505795