P5369 [PKUSC2018] Maximum Prefix Sum

Xiao C is an algorithm contest enthusiast. One day, Xiao C ran into a very difficult problem: finding the maximum subarray sum of a sequence. However, Xiao C cannot solve this problem, so Xiao C decides to randomly shuffle the sequence and then take the maximum prefix sum of the shuffled sequence as the answer. Xiao C knows very well that this algorithm is completely wrong, so he does not care about its correctness. He only cares about the expected value of the computed result. Please help him solve this problem. Since the answer may be very complicated, you only need to output the value of the answer multiplied by $n!$ and then taken modulo $998244353$. Obviously, this is an integer. Note: The definition of maximum prefix sum: $\forall i \in [1,n]$, the maximum value of $\sum_{j=1}^{i}a_j$.

The first line contains a positive integer $n$, which denotes the length of the sequence. The second line contains $n$ numbers, representing the original sequence $a[1..n]$. The $i$-th number is $a[i]$.

Output a **non-negative integer**, which denotes the answer.

For $10\%$ of the testdata, $1\leq n\leq 9$. For $40\%$ of the testdata, $1\leq n\leq 15$. For another $10\%$ of the testdata, in $a$ there is at most one negative number. For another $10\%$ of the testdata, $|a[i]|\leq 2$. For $100\%$ of the testdata, $1\leq n\leq 20$, $\sum_{i=1}^{n}|a[i]|\leq 10^9$. Translated by ChatGPT 5