This page is still under construction.

Parts of this page are still being built. What you see may change.

The Cross Covers Everything

Time limit3sMemory limit1024 MB

Summary
Count ordered point pairs whose cross, formed by the x-range and y-range between the two points, covers every given point.
Level

Medium6 of 10

Topics
Sorting, Prefix sum, Geometry
Solved
No attempts yet

Problem

A cross-shaped infinite area on the xx-yy plane is specified by two distinct points, as shown in the figure below.

Figure J.1. The cross area specified by points 2 and 4

Given a set of points on the plane, count the ordered pairs ⟨p,q⟩\langle p, q \rangle that cover all the points. The pair ⟨p,q⟩\langle p, q \rangle covers a point (x,y)(x, y) if xp≤x≤xqx_p \le x \le x_q, or yp≤y≤yqy_p \le y \le y_q, or both hold. No two points share an xx-coordinate or a yy-coordinate.

Input

The first line contains an integer nn (2≤n≤2×1052 \le n \le 2 \times 10^5), the number of points. Each of the following nn lines contains two integers xix_i and yiy_i (1≤xi≤1061 \le x_i \le 10^6, 1≤yi≤1061 \le y_i \le 10^6), the coordinates of the ii-th point. For all j≠kj \ne k, xj≠xkx_j \ne x_k and yj≠yky_j \ne y_k. The input is a single test case.

Output

Print the number of ordered pairs of points that cover all the points, on one line.

Hint

The cross in the figure is specified by the second and fourth points of the first sample input. It is one of the crosses covering all the points.

Examples2

  1. Example 1

    Input
    4
    2 1
    1 2
    6 3
    5 4
    
    Expected output
    4
    
  2. Example 2

    Input
    20
    15 9
    14 13
    2 7
    10 5
    11 17
    13 8
    9 3
    8 12
    6 4
    19 18
    12 1
    3 2
    5 10
    18 11
    4 19
    20 16
    16 15
    1 14
    7 6
    17 20
    
    Expected output
    9