题目描述
对于一个 1,2,…,n 的排列,令 si 表示包含数值 1,2,…,i 的最短连续子数组的长度。
设 pos(x) 为数值 x 在排列中的位置,则
$$s_i=\max_{1\le x\le i}\operatorname{pos}(x)-\min_{1\le x\le i}\operatorname{pos}(x)+1.$$
对于每个 i,给定区间约束 [li,ri]。请统计满足所有约束 li≤si≤ri 的排列数量,答案对 998244353 取模。
输入格式
第一行包含整数 n。
接下来 n 行,第 i 行包含两个整数 li,ri。
输出格式
输出一个整数,表示合法排列数量对 998244353 取模后的结果。可能不存在合法排列,此时输出 0。
样例
3
1 1
2 2
3 3
4
合法排列为 (1,2,3)、(2,1,3)、(3,1,2)、(3,2,1)。
数据范围
1≤n≤2×105,1≤li≤ri≤n。