Three Points

Time limit2sMemory limit512 MB

Summary

Count triples of points where the x coordinates increase and the y coordinates order as r < b < g.

Level: Medium7 of 10
Topics: Sorting, Prefix sum, Combinatorics
Solved: No attempts yet

Problem

There are N points on an infinite two-dimensional plane. The points are numbered 0 through N-1, and point i lies at $(x_i, y_i)$ . No two points share an x coordinate, and no two points share a y coordinate.

Pick three of the points and color one red, one green, and one blue. Let $r$ be the number of the red point, $g$ the number of the green point, and $b$ the number of the blue point. The coloring must satisfy $x_r < x_g < x_b$ and $y_r < y_b < y_g$ at the same time.

Given the coordinates of the points, write a program that counts the colorings satisfying both conditions.

Input

The first line contains N. Each of the next N lines contains the coordinates $x$ and $y$ of one point, separated by a space. ( $1 \le N \le 300{,}000$ , $0 \le x, y < 1{,}000{,}000{,}000$ )

Output

Print the number of colorings that satisfy the conditions. This value can exceed the range of a 32-bit integer.

Examples5

Example 1

Input

Expected output

Example 2
Input
```
1
5 7
```
Expected output
```
0
```
Example 3
Input
```
2
0 1
1 0
```
Expected output
```
0
```
Example 4
Input
```
3
0 0
1 2
2 1
```
Expected output
```
1
```
Example 5
Input
```
3
0 0
1 1
2 2
```
Expected output
```
0
```