#P5369. [PKUSC2018] 最大前缀和

[PKUSC2018] 最大前缀和

题目描述

小 C 是一个算法竞赛爱好者,有一天小 C 遇到了一个非常难的问题:求一个序列的最大子段和。

但是小 C 并不会做这个题,于是小 C 决定把序列随机打乱,然后取序列的最大前缀和作为答案。

小 C 是一个非常有自知之明的人,他知道自己的算法完全不对,所以并不关心正确率,他只关心求出的解的期望值,现在请你帮他解决这个问题,由于答案可能非常复杂,所以你只需要输出答案乘上 n!n! 后对 998244353998244353 取模的值,显然这是个整数。

注:最大前缀和的定义:i[1,n]\forall i \in [1,n]j=1iaj\sum_{j=1}^{i}a_j的最大值。

输入格式

第一行一个正整数 nn,表示序列长度。

第二行 nn 个数,表示原序列 a[1..n]a[1..n],第 ii 个数表示 a[i]a[i]

输出格式

输出一个非负整数,表示答案。

2
-1 2
3

提示

对于10%10\%的数据,有1n91\leq n\leq 9

对于40%40\%的数据,有1n151\leq n\leq 15

另有10%10\%的数据,满足aa中最多只有一个负数。

另有10%10\%的数据,满足a[i]2|a[i]|\leq 2

对于100%100\%的数据,满足1n201\leq n\leq 20i=1na[i]109\sum_{i=1}^{n}|a[i]|\leq 10^9