橋の建設
都市の中心部を横切る美しい川が流れる街があります。この街の市当局は、街をつなぐための橋を建設することを決めました。現在、人々は川を渡る際にボートを利用していますが、これはあまり便利ではありません。
この街では、橋で結ぶことができる可能性がある
n 組の座標を特定しています。ただし、橋同士が交差しない（ある橋がほかの橋をまたいで交差しない）という条件があります。一方で、橋の始点や終点が同じになることは許容されます。与えられた座標ペアを基に、この条件を満たしながら市当局が建設できる橋の最大本数を求めることが課題となります。
🌊
座標について:
この川を座標系のOX軸として考えることができます。
都市がある2つの地域は、X軸より上側と下側に分かれています。したがって、ここで示される座標は橋の始点・終点となる
x座標を表します。入力
入力の最初の行には、整数
n (1 ≤ n ≤ 100 000) が1つ与えられます。続く
n 行には、それぞれ橋で結びうる座標を表す整数の組 が与えられます (1 ≤ ≤ )。出力
プログラムは、市当局が条件を満たして建設できる橋の最大本数を、整数で1つ出力してください。
例
Input | Output |
4
2 6
5 4
8 1
10 2 | 2 |
6
1 3
2 4
3 5
4 6
5 1
6 2 | 4 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB