配点 : $600$ 点

問題文

縦 $N$ マス、横 $N$ マスのグリッドがあります。上から $i$ 行目、左から $j$ 列目のマスをマス$(i,j)$ と表します。

グリッドの中央 $(N-2)\times (N-2)$ マスには黒い石が $1$ 個ずつ置いてあり、下辺と右辺の計 $2N-1$ マスには白い石が $1$ 個ずつ置いてあります。

$Q$ 個のクエリが与えられるので、順番に処理してください。 クエリには $2$ 種類あり、入力形式とクエリの内容は以下のとおりです。

• 1 x： $(1,x)$ に白い石を置く。そこから下方向に最も近い白い石との間にある黒い石を全て白い石に置き換える
• 2 x： $(x,1)$ に白い石を置く。そこから右方向に最も近い白い石との間にある黒い石を全て白い石に置き換える

$Q$ 個のクエリを全て処理したあとグリッド上に黒い石はいくつありますか。

制約

• $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$
• 同じクエリが複数回与えられることはない

入力

入力は以下の形式で標準入力から与えられる。

$N$ $Q$

$Query_1$

$\vdots$

$Query_Q$

出力

$Q$ 個のクエリを全て処理したあとグリッド上にある黒い石の個数を出力せよ。

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

1

各クエリにより、グリッドは次のように変化します。

200000 0

39999200004

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

31159505795