Nested Interval Operations Sum

You are given an array of 2n integers: \(a_1,a_2,\dots,a_{2n}\). You need to form n intervals \([l_i,r_i]\) such that:

• The 2n numbers \(l_1, r_1, l_2, r_2,\dots, l_n, r_n\) form a permutation of \(\{1,2,\dots,2n\}\).
• \(l_1 < l_2 < \cdots < l_n\).
• For any two intervals, they are either disjoint or one is contained in the other. In other words, for any two intervals \([l_i,r_i]\) and \([l_j,r_j]\), we have either \([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]\).

For each interval \([l_i,r_i]\), its difficulty is defined as \(a_{l_i}\times a_{r_i}\). The total difficulty of a particular configuration is the sum of difficulties of all intervals. Your task is to compute the sum of difficulties over all valid configurations, modulo \(998244353\).

Note: The condition on intervals implies that the intervals must form a structure identical to a valid parentheses matching (also known as non-crossing matching). Thus, you should consider the usual Catalan structure and use dynamic programming to solve the problem.

Formally:

Given an array \(a_1,a_2,\dots,a_{2n}\), let a configuration be defined by n intervals \([l_i,r_i]\) with \(1\le l_i<r_i\le 2n\) that satisfy:

1. \(l_1, r_1, l_2, r_2, \dots, l_n, r_n\) is a permutation of \(\{1,2,\dots,2n\}\).
2. \(l_1<l_2<\dots<l_n\).
3. For every \(i,j\), either \([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]\).

You need to compute the following value modulo \(998244353\):

\[ \sum_{\text{valid configurations}} \;\sum_{i=1}^n \; a_{l_i}\times a_{r_i}. \]</p>

inputFormat

The first line contains a single integer \(n\) indicating that there are \(2n\) numbers.

The second line contains \(2n\) space-separated integers \(a_1,a_2,\dots,a_{2n}\).

outputFormat

Output a single integer, the sum of difficulties over all valid configurations modulo \(998244353\).

sample

1
1 2

2