[PKUSC2018]最大前缀和

题目描述

小 C 是一个算法竞赛爱好者,有一天小 C 遇到了一个非常难的问题:求一个序列的最大子段和。 但是小 C 并不会做这个题,于是小 C 决定把序列随机打乱,然后取序列的最大前缀和作为答案。 小 C 是一个非常有自知之明的人,他知道自己的算法完全不对,所以并不关心正确率,他只关心求出的解的期望值,现在请你帮他解决这个问题,由于答案可能非常复杂,所以你只需要输出答案乘上 $n!$ 后对 $998244353$ 取模的值,显然这是个整数。 注:最大前缀和的定义:$\forall i \in [1,n]$,$\sum_{j=1}^{i}a_j$的最大值。

输入输出格式

输入格式


第一行一个正整数 $n$,表示序列长度。 第二行 $n$ 个数,表示原序列 $a[1..n]$,第 $i$ 个数表示 $a[i]$ 。

输出格式


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

输入输出样例

输入样例 #1

2
-1 2

输出样例 #1

3

说明

对于$10\%$的数据,有$1\leq n\leq 9$。 对于$40\%$的数据,有$1\leq n\leq 15$。 另有$10\%$的数据,满足$a$中最多只有一个负数。 另有$10\%$的数据,满足$|a[i]|\leq 2$。 对于$100\%$的数据,满足$1\leq n\leq 20$,$\sum_{i=1}^{n}|a[i]|\leq 10^9$。