题解

• 模型：将区间按左端点排序，设公共长度为 $L$，左端点为升序数组 $a_1,\dots,a_n$。

• 相交判定：两个区间相交当且仅当左端点差小于 $L$。

• 预处理：

  • $next[i]$ = $min(j>i \mid a_j \ge a_i + L)$（选择第 $i$ 个后，下一次能选的最左位置）。
  • $R[i] = next[i]-1$（第 $i$ 个被选区间向右能覆盖到的最远下标）。

• DP 定义：$f[i]$ 表示从第 $i$ 个“尚未被覆盖”的区间开始，选出一组满足条件的方案数。

• 关键转移：第 $i$ 个必须被某个 $j\in[i, R[i]]$ 覆盖，于是

题目内容

对于给定的$n$个长度相同的区间，第$i$个区间的左端点为$l_i$，

右端点为$r_i$，且全部区间的长度$r_i-l_i+1$固定。

你需要从中任选若干个不同的区间，使得:

• 选定的区间两两不存在交集;
• 其余区间均至少与一个选定的区间存在交集。

一共有多少种不同的选择方案?由于答案可能很大，请将答案对$998\ 244\ 353$取模后输出。

[名词解释]

交集: 我们定义两个闭区间$[l_1,r_1]$和$[l_2,r_2]$存在交集，当且仅当 $max(l_1,l_2) ≦min(r_1,r_2)$。换言之，仅在端点处重合也视为存在交集。

输入描述

第一行输入一个整数$n(2 ≦n≦10^5)$代表区间的数量。

此后$n$ 行，第$i$行输入两个整数$l_i$和$r_i(1 ≦l_i≦r_i≦2×10^9)$代表第$i$个区间的左端点和右端点。

保证所有区间的长度相同。

输出描述

输出一个整数，代表一共有多少种不同的选择方案。由于答案可能很大，请将答案对$998\ 244\ 353$取模后输出。

样例1

输入

3
1 3
2 4
3 5

输出

3

说明

在这个样例中，一共有三种不同的选择方案:

• 单单选择第$1$个区间;
• 单单选择第$2$个区间;
• 单单选择第$3$个区间。

样例2

输入

3
1 2
3 4
5 6

输出

1 

说明

在这个样例中，唯一的选择方案是同时选择全部区间。

样例3

输入

7
10 13
1 4
9 12
5 8
4 7
7 10
8 11

输出

7