You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

给定 $n$ 个数轴上的闭区间，请统计有多少对区间的交集不是空集。

输入格式

• 第一行：一个整数 $n$；
• 接下来 $n$ 行：每行两个整数 $a_i$ 与 $b_i$，表示一个闭区间的左端点与右端点。

输出格式

• 单个整数：表示有多少对区间的交集不是空集。

3
1 10
1 4 
5 12

2

2
1 2
2 3

1

说明

两个闭区间的交可能只有一个数字，在这种情况下，也是符合非空要求的。

数据范围

• 对于 30% 的数据，$1 \le n \le 5\,000$；
• 对于 60% 的数据，$1 \le n \le 20\,000$；
• 对于 100% 的数据，$1 \le n \le 300\,000$；
• $1 \le a_i \le b_i \le 1\,000\,000$。