配点 : $500$ 点

問題文

二次元平面上の第一象限上に $N$ 個のフの字があります。

$i\ (1 \leq i \leq N)$ 個目のフの字は、$(x_i-1,y_i)$ と $(x_i,y_i)$ を結ぶ線分と $(x_i,y_i-1)$ と $(x_i,y_i)$ を結ぶ線分の $2$ つを組み合わせた図形です。

あなたは、$N$ 個のフの字から $0$ 個以上を選び、削除することができます。

適切に削除するフの字を選んだとき、原点から全体が見えるフの字の個数は最大でいくつになりますか？

ここで、原点からあるフの字（便宜上 $i$ 個目のフの字とする）の全体が見える必要十分条件は、以下の通りです。

• 原点、$(x_i-1,y_i)$、$(x_i,y_i)$、$(x_i,y_i-1)$ の $4$ 点を頂点とする四角形の内部（境界を除く）と他のフの字が共通部分を持たない。

制約

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq x_i,y_i \leq 10^9$
• $(x_i,y_i) \neq (x_j,y_j)\ (i \neq j)$
• 入力はすべて整数

入力

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

$N$

$x_1$ $y_1$

$x_2$ $y_2$

$\hspace{0.45cm}\vdots$

$x_N$ $y_N$

出力

原点から全体が見えるフの字の個数の最大値を出力せよ。

3
1 1
2 1
1 2

2

$1$ 個目のフの字を削除したとき原点からは $2$ 個目のフの字と $3$ 個目のフの字の $2$ つが見えるようになり、これが最大です。

$1$ つのフの字も削除しない場合、原点からは $1$ 個目のフの字のみしか見えません。

10
414598724 87552841
252911401 309688555
623249116 421714323
605059493 227199170
410455266 373748111
861647548 916369023
527772558 682124751
356101507 249887028
292258775 110762985
850583108 796044319

10

すべてのフの字を削除せずに残すのが最善です。