AT_abc273_h [ABC273Ex] Inv(0,1)ving Insert(1,0)n

时间限制6.00s 内存限制1.00GB

题目描述

给定一个由 $N$ 个整数组成的序列 $S=((a_1,b_1),(a_2,b_2),\cdots,(a_N,b_N))$，并且 $S$ 的元素是不同的。 $S$ 的连续子序列 $S_l,r=((a_l,b_l),(a_l+1,b_l+1),...,(a_r,b_r))$ 有 $N×(N+1)\div2$ 个可能。我们需要计算所有 $f(S_l,r)$ 的和，其中 $f(S_l,r)$ 是使 $S$ 的所有元素都包含在 $A$ 中所需的最小操作次数，$A$ 是如下定义的序列： $A = ((0,1),(1,0))$

具体而言，f(S_l,r) = （使得S_l,r的所有元素都包含在A中所需的最小操作次数）。

如果这样的操作不存在，$f(S_l,r) = 0$。

最后，将所得结果取模 $998244353$ 后输出。

输入格式

输入的第一行包含一个整数 $N$。

接下来的 $N$ 行，每行包含两个整数 $a_i$ 和 $b_i$，表示序列 $S$ 中的元素。

输出格式

输出一个整数，表示取模 $998244353$ 后的答案。

输入输出样例 #1

输入 #1

7
1 2
3 7
3 5
0 0
1000000000 1
0 1
6 3

输出 #1

3511324

说明/提示

对于 $30\%$ 的数据，$2 \le N \le 5$； 对于 $100\%$ 的数据，$2 \le N \le 10^3，0 \le a_i, b_i \le 10^9$。

输入输出样例

输入样例：

2
0 1
1 0

输出样例：

3