BZPRO
#5369. [Pkusc2018]最大前缀和
内存限制：512 MiB
时间限制：20 Sec
提交
提交记录
讨论
题目描述
小C是一个算法竞赛爱好者，有一天小C遇到了一个非常难的问题：求一个序列的最大子段和。
但是小C并不会做这个题，于是小C决定把序列随机打乱，然后取序列的最大前缀和作为答案。
小C是一个非常有自知之明的人，他知道自己的算法完全不对，所以并不关心正确率，他只关心求出的解的期望值，
现在请你帮他解决这个问题，由于答案可能非常复杂，所以你只需要输出答案乘上n!后对998244353取模的值，显然这是个整数。
注：最大前缀和的定义：i∈[1,n],Sigma(a
j
)的最大值,其中1<=j<=i
输入格式
第一行一个正整数nnn，表示序列长度。
第二行n个数，表示原序列a[1..n]，第i个数表示a[i]。
1≤n≤20,Sigma(|Ai|)<=10^9,其中1<=i<=N
输出格式
输出一个非负整数，表示答案。
样例
样例输入
2
-1 2
样例输出
3
数据范围与提示
BZPRO