「CGOI-3」残暴圣所
题目背景
终于打过春二心门的 ac 来到了春三，并决定预测一下残暴圣所（Ferocious Sanctuary）的难度。
[](//www.bilibili.com/video/BV1Cg411v7Ji)
题目描述
为了通关残暴圣所，ac 需要在接下来的 $2n$ 个时刻进行 $n$ 次操作。第 $i$ 次操作需要在时刻 $l_i$ 按下某个按键，此后一直按住这个按键，直到时刻 $r_i$ 松开它（$l_i<r_i$）。在每个时刻，ac 要么按下一个按键，要么松开一个按键，但是可以同时按住多个按键。
第 $i$ 次操作形成了一个操作区间 $[l_i,r_i]$，满足 $l_i$ 严格递增。并且，由于残暴圣所的关卡设计，任意两个操作形成的操作区间之间，要么不交，要么包含。
ac 设计了 $2n$ 个难度系数 $a_1,a_2,\dots,a_{2n}$。第 $i$ 次操作的难度可以用 $a_{l_i}\times a_{r_i}$ 来评估，而通关残暴圣所的难度即为所有操作的难度之和。
然而，由于 ac 卡在了残暴圣所的第一面，所以他并不知道每个操作的操作区间。在给定 $n$ 和 $\{a\}$ 的前提下，请你计算对于所有可能的情况，通关残暴圣所的难度之和，对 $998244353$ 取模。
#### 形式化题意：
给定一个长为 $2n$ 的数列 $a_1,a_2,\dots,a_{2n}$。
定义“区间组”由 $n$ 个区间组成，第 $i$ 个区间为 $[l_i,r_i]\ (1\le l_i<r_i\le2n)$，求所有满足下列条件的区间组的 $\sum_{i=1}^na_{l_i}\times a_{r_i}$ 之和对 $998244353$ 取模：
1. $l_1,r_1,l_2,r_2,\dots,l_n,r_n$ 是 $1,2,\dots,2n$ 的一个排列。
2. $\forall 1\le i<n$，$l_i<l_{i+1}$。
3. $\forall i,j$，$[l_i,r_i]\cap[l_j,r_j]=\varnothing$ 或 $[l_i,r_i]\sube[l_j,r_j]$ 或 $[l_j,r_j]\sube[l_i,r_i]$。
输入输出格式
输入格式
第一行一个整数 $n$，表示区间数。
第二行 $2n$ 个整数 $a_i$，含义如上所述。
输出格式
一行一个整数，表示答案对 $998244353$ 取模的值。
输入输出样例
输入样例 #1
2
114 514 1919 810输出样例 #1
2691692输入样例 #2
3
1 1 4 5 1 4输出样例 #2
98输入样例 #3
8
275272885 418731188 289662326 114331587 192436268 885936831 877490593 508774565 633402863 149033362 995239139 494498006 168828873 138947653 983144753 844326228输出样例 #3
349824160说明
#### 样例说明
对于样例 1，可能的两个操作区间只有两种情况：
1. $[1,2],[3,4]$，通关难度为 $a_1a_2+a_3a_4=1612986$。
2. $[1,4],[2,3]$，通关难度为 $a_1a_4+a_2a_3=1078706$。
难度之和为 $1612986+1078706=2691692$，对 $998244353$ 取模后仍为 $2691692$。
以下几种情况是不合法的：
1. $[3,4],[1,2]$，因为要求 $l_i$ 严格递增，而 $l_1\ge l_2$。
2. $[1,1],[2,4]$，因为要求 $l_i<r_i$，而 $l_1\ge r_1$。
3. $[1,3],[2,3]$，因为要求在每个时刻，要么按下一个按键，要么松开一个按键，而第三个时刻松开了两个按键，第四个时刻没有按下或松开任何一个按键。
4. $[1,3],[2,4]$，因为要求任意两个操作区间不交或包含，而这两个区间之间有交，并且没有包含关系。
---
#### 数据范围
对于 $10\%$ 的数据，$n\le15$。
对于 $30\%$ 的数据，$n\le200$。
对于 $50\%$ 的数据，$n\le3000$。
对于另 $5\%$ 的数据，$a_i=1$。
对于 $100\%$ 的数据，$1\le n\le5\times10^5$，$0\le a_i<998244353$。