一个结论：“从出发点开始走绝对不会出现死循环”。

考虑如何证明这个结论（这会直接提示正解）：

我们对数轴分段，对于任意一个传送门，把当前段分成两段。

对于每一段（除了第一段）我们总会有一个到达这个段的方法：走一个传送门。这个传送门的位置是这个段左边第一个传送门，我们查看这个传送门通向哪里，然后把那个点与这个点连一条有向边。

对于每一段（除了最后一段）我们总会有一个离开这个段的方法，和上面类似建图。

我们考虑，我们在行走过程中，由于第一个段没有入度，所以我们绝对不会回到第一个段。

由于最后一个段没有出度，所以我们绝对不会向其他地方循环。

由于除了开头和结尾的特殊段，其他任何段有且仅有一个入度和出度，所以我们一定会从一号段到达最后一个段离开。

证毕。

我们发现，除了从一号点到最后一个点是一条简单路径，其他的点一定在一个环里（可以画图理解）。

考虑我们新加一个传送门，会导致这张有向图如何变化？

我们有三种加的方式：

• 一：用一对传送门把两个不在同一个连通块的点链接。
  这会直接导致有两个点一分为二，然后他们所在的连通块合并。
  如果我们合并路径和环，我们会得到一个更长的路径。
  如果我们合并环和环，我们会得到一个更大的环。
• 二：用一对传送门链接同一个连通块里两个点。
  这会直接导致这个连通块一分为二。这对答案没有任何帮助。
• 三：这对传送门放在某对传送门的内部，这会导致我们永远无法访问到这个传送门，所以他单独成一个点。

题解显而易见，我们把所有环从大到小排序。

然后从大到小，用传送门把他们用方法一连到我们的路径里。

如果连完以后，传送门还有剩余，我们可以不断做方法三和方法一，把他们累加到答案里。

细节：如果只剩一个传送门，我们就把他加在末尾。

时间复杂度\(O(nlogn)\)

进一步优化：

我们发现复杂度瓶颈在于排序，但是由于排序的值非常小，我们使用桶排序。

时间复杂度到达理论下届：\(O(n)\)

但是我懒得写线性的，下面给出\(O(nlogn)\)的代码，吸氧能过。

#include
    
     using namespace std;const int maxn = 2e6+10;struct qwq {    int inc,out;}s[maxn];struct QQQ {    int l,r;}L[maxn];struct QAQ {    int v,bl,type;    const bool operator < (const QAQ& rhs) const {        return v