Description:


对于一个区间集合

我们定义其权值:

当然,如果这些区间没有交集则权值为0。

Input:


给你N个各不相同的区间,请你从中找出若干个区间使其权值最大。
第一行N
接下来N行 l r(1<=l<r<=10^6)

Output:


最大权值

Sample Input:


Sample Output:


HINT:


100% \(1\lt N\le 10^6\)

题解:


仔细观察一下,发现如果有三个或以上的区间,总是不如两个优。

所以我们可以只用考虑用两个区间来更新答案。

把所有区间排序,去除包含关系的。

就可以用单调队列DP一下了。