P14862 [ICPC 2021 Yokohama R] The Cross Covers Everything

A cross-shaped infinite area on the $x-y$ plane can be specified by two distinct points as depicted on the figure below. :::align{center}  Figure J.1. The cross area specified by two points numbered 2 and 4 ::: Given a set of points on the plane, you are asked to figure out how many pairs of the points form a cross-shaped area that covers all the points. To be more precise, when $n$ points with coordinates $(x_i, y_i)$ ($i = 1, \dots, n$) are given, the ordered pair $\langle p, q \rangle$ is said to cover a point $(x, y)$ if $x_p \leq x \leq x_q$, $y_p \leq y \leq y_q$, or both hold. Your task is to find how many pairs $\langle p, q \rangle$ cover all the $n$ points. No two given points have the same $x$-coordinate nor the same $y$-coordinate.

The input consists of a single test case of the following format. $$ \begin{aligned} &n \\ &x_1\ y_1 \\ &\vdots \\ &x_n\ y_n \end{aligned} $$ The first line contains an integer $n$ ($2 \leq n \leq 2 \times 10^5$), which is the number of points given. Two integers $x_i$ and $y_i$ in the $i$-th line of the following $n$ lines are the coordinates of the $i$-th point ($1 \leq x_i \leq 10^6$, $1 \leq y_i \leq 10^6$). You may assume that $x_j \neq x_k$ and $y_j \neq y_k$ hold for all $j \neq k$.

Print in a line the number of ordered pairs of points that satisfy the condition.

Figure J.1 depicts the cross specified by two points numbered 2 and 4, that are the second and the fourth points of the Sample Input 1. This is one of the crosses covering all the points. ### Amendment The conditions $x_p \leq x_q$, and $y_p \leq y_q$, have to be added to be satisfied for the ordered pair $\langle p, q \rangle$ that are counted. This was announced during the contest.