Problem Background

After finally defeating the Spring II Heart Gate, ac has reached Spring III and decided to predict the difficulty of the Ferocious Sanctuary.

Problem Description

To clear the Ferocious Sanctuary, ac needs to perform \( n \) operations over the next \( 2n \) moments. The \( i \)-th operation requires pressing a key at moment \( l_i \) and holding it until moment \( r_i \) (where \( l_i < r_i \)). At each moment, ac either presses or releases a key, but can hold multiple keys simultaneously.

The \( i \)-th operation forms an operation interval \([l_i, r_i]\), with \( l_i \) strictly increasing. Due to the level design of the Ferocious Sanctuary, any two operation intervals either do not intersect or one is contained within the other.

ac has designed \( 2n \) difficulty coefficients \( a_1, a_2, \dots, a_{2n} \). The difficulty of the \( i \)-th operation can be evaluated using \( a_{l_i} \times a_{r_i} \), and the difficulty of clearing the Ferocious Sanctuary is the sum of the difficulties of all operations.

However, since ac is stuck at the first stage of the Ferocious Sanctuary, he does not know the operation intervals for each operation. Given \( n \) and the sequence \(\{a\}\), please calculate the sum of the difficulties for all possible scenarios, modulo \( 998244353 \).

Formal Problem Statement:

Given a sequence of length \( 2n \), \( a_1, a_2, \dots, a_{2n} \).

Define a "set of intervals" consisting of \( n \) intervals, where the \( i \)-th interval is \([l_i, r_i]\) (\( 1 \le l_i < r_i \le 2n \)). Find the sum of \(\sum_{i=1}^n a_{l_i} \times a_{r_i}\) for all sets of intervals that satisfy the following conditions, modulo \( 998244353 \):

1. \( l_1, r_1, l_2, r_2, \dots, l_n, r_n \) is a permutation of \( 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\) or \([l_i, r_i] \subseteq [l_j, r_j]\) or \([l_j, r_j] \subseteq [l_i, r_i]\).

Input Format

The first line contains an integer \( n \), the number of intervals.

The second line contains \( 2n \) integers \( a_i \), as described above.

Output Format

Output a single integer, the answer modulo \( 998244353 \).

Sample Input and Output

Sample Input #1

2
114 514 1919 810

Sample Output #1

2691692

Sample Input #2

3
1 1 4 5 1 4

Sample Output #2

98

Sample Input #3

8
275272885 418731188 289662326 114331587 192436268 885936831 877490593 508774565 633402863 149033362 995239139 494498006 168828873 138947653 983144753 844326228

Sample Output #3

349824160

Notes

Sample Explanation

For Sample 1, the only two possible sets of operation intervals are:

1. \([1, 2], [3, 4]\), with a difficulty of \( a_1a_2 + a_3a_4 = 1612986 \).
2. \([1, 4], [2, 3]\), with a difficulty of \( a_1a_4 + a_2a_3 = 1078706 \).

The sum of difficulties is \( 1612986 + 1078706 = 2691692 \), which remains \( 2691692 \) modulo \( 998244353 \).

The following scenarios are invalid:

1. \([3, 4], [1, 2]\), because \( l_i \) must be strictly increasing, and \( l_1 \ge l_2 \).
2. \([1, 1], [2, 4]\), because \( l_i < r_i \) is required, and \( l_1 \ge r_1 \).
3. \([1, 3], [2, 3]\), because at each moment, either a key is pressed or released, and at the third moment two keys are released, and at the fourth moment no key is pressed or released.
4. \([1, 3], [2, 4]\), because any two operation intervals must either not intersect or one must contain the other, and these intervals intersect without containment.

Data Range

For \( 10\% \) of the data, \( n \le 15 \).

For \( 30\% \) of the data, \( n \le 200 \).

For \( 50\% \) of the data, \( n \le 3000 \).

For another \( 5\% \) of the data, \( a_i = 1 \).

For \( 100\% \) of the data, \( 1 \le n \le 5 \times 10^5 \), \( 0 \le a_i < 998244353 \).

见题面 Input 部分

见题面 Output 部分