There are $n$ points on the plane, the $i$-th of which is at $(x_i, y_i)$. Tokitsukaze wants to draw a strange rectangular area and pick all the points in the area.

The strange area is enclosed by three lines, $x = l$, $y = a$ and $x = r$, as its left side, its bottom side and its right side respectively, where $l$, $r$ and $a$ can be any real numbers satisfying that $l < r$. The upper side of the area is boundless, which you can regard as a line parallel to the $x$-axis at infinity. The following figure shows a strange rectangular area. [Image] 

A point $(x_i, y_i)$ is in the strange rectangular area if and only if $l < x_i < r$ and $y_i > a$. For example, in the above figure, $p_1$ is in the area while $p_2$ is not.

Tokitsukaze wants to know how many different non-empty sets she can obtain by picking all the points in a strange rectangular area, where we think two sets are different if there exists at least one point in one set of them but not in the other.


-----Input-----

The first line contains a single integer $n$ ($1 \leq n \leq 2 \times 10^5$) — the number of points on the plane.

The $i$-th of the next $n$ lines contains two integers $x_i$, $y_i$ ($1 \leq x_i, y_i \leq 10^9$) — the coordinates of the $i$-th point.

All points are distinct.


-----Output-----

Print a single integer — the number of different non-empty sets of points she can obtain.


-----Examples-----
Input
3
1 1
1 2
1 3

Output
3

Input
3
1 1
2 1
3 1

Output
6

Input
4
2 1
2 2
3 1
3 2

Output
6



-----Note-----

For the first example, there is exactly one set having $k$ points for $k = 1, 2, 3$, so the total number is $3$.

For the second example, the numbers of sets having $k$ points for $k = 1, 2, 3$ are $3$, $2$, $1$ respectively, and their sum is $6$.

For the third example, as the following figure shows, there are  $2$ sets having one point;  $3$ sets having two points;  $1$ set having four points. 

Therefore, the number of different non-empty sets in this example is $2 + 3 + 0 + 1 = 6$. [Image]

Source: codeforces | Difficulty: HARD
Tags: Data structures

Sorting

Amortized analysis

Divide and conquer


Solutions:
import sys
import copy
input = sys.stdin.readline
n = int(input())
P = [list(map(int, input().split())) for i in range(n)]
SET_X = set()
SET_Y = set()
for (x, y) in P:
	SET_X.add(x)
	SET_Y.add(y)
CX = sorted(SET_X)
CY = sorted(SET_Y)
LEN = len(CX)
MAX = len(CX) - 1
DICT_X = {x: i for (i, x) in enumerate(CX)}
DICT_Y = {x: i for (i, x) in enumerate(CY)}
for i in range(n):
	P[i] = [DICT_X[P[i][0]], DICT_Y[P[i][1]]]
check = [0] * len(CX)
BIT = [0] * (LEN + 1)

def update(v, w):
	while v <= LEN:
		BIT[v] += w
		v += v & -v

def getvalue(v):
	ANS = 0
	while v != 0:
		ANS += BIT[v]
		v -= v & -v
	return ANS
LIST_Y = [[] for i in range(len(CY))]
for (x, y) in P:
	LIST_Y[y].append(x)
for i in range(len(CY)):
	LIST_Y[i].sort()
ANS = 0
for y in range(len(CY) - 1, -1, -1):
	for x in LIST_Y[y]:
		if check[x] == 0:
			check[x] = 1
			update(x + 1, 1)
	ANS += getvalue(LIST_Y[y][0] + 1) * (getvalue(MAX + 1) - getvalue(LIST_Y[y][0] + 1) + 1)
	for i in range(1, len(LIST_Y[y])):
		ANS += (getvalue(LIST_Y[y][i] + 1) - getvalue(LIST_Y[y][i - 1] + 1)) * (getvalue(MAX + 1) - getvalue(LIST_Y[y][i] + 1) + 1)
print(ANS)