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.