Scarecrows

x좌표와 y좌표가 각각 서로 다른 N개의 점이 주어질 때, 남서쪽과 북동쪽 꼭짓점이 점이고 내부에 다른 점이 없는 축에 평행한 직사각형의 개수를 센다.

어려움8정렬분할 정복세그먼트 트리아직 제출이 없습니다시간 제한4초메모리 제한512 MB

문제

JOI 村にある広い荒れ地には N 体のかかしが立っており,村民は年に数回,かかしたちを囲ってお祭り を行っていた.あるとき,かかしたちのお告げを聞いたという JOI 村の村長は,荒れ地に畑を 1 つ作る計 画を立てた.お告げによると,畑は以下の条件を満たすべきであるという:

  • 各辺が,東西方向あるいは南北方向であるような長方形である.
  • 南西の頂点および北東の頂点には,かかしが立っている.
  • 畑の内部 (境界を除く) には,かかしは立っていない.

もちろん,大切なかかしたちを動かすことは許されない.お告げに従った畑の場所はいくつあるだろうか.

かかしたちの位置が与えられたとき,お告げに従った畑の場所の個数を求めるプログラムを作成せよ.

입력

標準入力から以下のデータを読み込め.

  • 1 行目には,整数 N が書かれており,かかしが N 体立っていることを表す.
  • 続く N 行のうちの i 行目 (1 ≤ i ≤ N) には,整数 Xi, Yi が空白を区切りとして書かれている.JOI 村の 荒れ地は xy 座標平面で表され,x 軸正の向きが東方向,y 軸正の向きが北方向である.i 番目のかか しは,座標 (Xi, Yi) に立っている.

출력

標準出力に,お告げに従った畑の場所の個数を 1 行で出力せよ.

제한

  • 1 ≤ N ≤ 200 000.
  • 0 ≤ Xi ≤ 1 000 000 000 (1 ≤ i ≤ N) .
  • 0 ≤ Yi ≤ 1 000 000 000 (1 ≤ i ≤ N) .
  • Xi (1 ≤ i ≤ N) は互いに異なる.
  • Yi (1 ≤ i ≤ N) は互いに異なる.