Score : $400$ points

问题陈述

给定 $N$ 个实数区间。第 $i$ 个 $(1 \leq i \leq N)$ 区间是 $[l_i, r_i]$。找出满足第 $i$ 个和第 $j$ 个区间相交的 $(i, j)$ 对的数量，其中 $(1 \leq i < j \leq N)$。

以上为大语言模型 kimi 翻译，仅供参考。

Problem Statement

You are given $N$ intervals of real numbers. The $i$-th $(1 \leq i \leq N)$ interval is $[l_i, r_i]$. Find the number of pairs $(i, j)\,(1 \leq i < j \leq N)$ such that the $i$-th and $j$-th intervals intersect.

Constraints

• $2 \leq N \leq 5 \times 10^5$
• $0 \leq l_i < r_i \leq 10^9$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

$N$

$l_1$ $r_1$

$l_2$ $r_2$

$\vdots$

$l_N$ $r_N$

Output

Print the answer.

Sample Input 1

3
1 5
7 8
3 7

Sample Output 1

2

The given intervals are $[1,5], [7,8], [3,7]$. Among these, the $1$-st and $3$-rd intervals intersect, as well as the $2$-nd and $3$-rd intervals, so the answer is $2$.

Sample Input 2

3
3 4
2 5
1 6

Sample Output 2

3

Sample Input 3

2
1 2
3 4

Sample Output 3

0