Description

Farmer John’s largest pasture can be viewed as a huge two-dimensional grid made of square cells (imagine a huge chessboard). Now, there are $N$ cows occupying some of the cells ($1 \le N \le 2500$).

Farmer John wants to build a fence that encloses a rectangular region; this rectangle must have its four sides parallel to the $x$-axis and the $y$-axis, and it must contain at least one cell. Please help him compute the number of different subsets of cows that he can enclose in such a region. Note that the empty set should be counted as one of the answers.

Input Format

The first line of input contains an integer $N$. The next $N$ lines each contain two space-separated integers, indicating the coordinates $(x,y)$ of the cell occupied by a cow. All $x$ coordinates are distinct, and all $y$ coordinates are distinct. All values of $x$ and $y$ are in the range $0 \ldots 10^9$.

Output Format

Output the number of subsets of cows that FJ can enclose. It can be proven that this number fits in a 64-bit signed integer type (for example, long long in C/C++).

4
0 2
1 0
2 3
3 5

13

Hint

There are $2^4$ subsets in total. FJ cannot build a fence that encloses only cows $1$, $2$, and $4$, or only cows $2$ and $4$, or only cows $1$ and $4$, so the answer is $2^4 - 3 = 16 - 3 = 13$.

• Testdata 2-3 satisfy $N \le 20$.
• Testdata 4-6 satisfy $N \le 100$.
• Testdata 7-12 satisfy $N \le 500$.
• Testdata 13-20 have no additional constraints.

Problem by: Benjamin Qi.

Translated by ChatGPT 5