题目描述
有 $n$ 个魔法石，第 $i$ 个魔力为 $w_i$。
对第 $i(2\le i\le n-1)$ 个魔法石可以进行扩散操作：
获得 $k=w_{i-1}+2w_i+w_{i+1}$ 点魔力。
$w_i$ 减少 $2k$，$w_{i-1}$ 和 $w_{i+1}$ 均增加 $k$。
求能获得魔力的最大值，对 $998244353$ 取模。
输入格式
第一行一个整数 $n$，代表魔法石数量。
第二行 $n$ 个整数，第 $i$ 个为 $w_i$。
输出格式
一行一个整数能获得魔力的最大值，对 $998244353$ 取模。
样例输入 #1
4
1 2 3 4样例输出 #1
20样例 #2/#3/#4
数据范围&提示
本题采用捆绑测试
对于 $100\%$ 数据，$3\le n\le10^6,|w_i|\le10^9$
| Subtask | 分值 | $n\le$ | 特殊性质 |
|---|---|---|---|
| $1$ | $10$ | $10$ | / |
| $2$ | $20$ | $10^4$ | / |
| $3$ | $20$ | $10^6$ | A |
| $4$ | $30$ | $5\times10^5$ | / |
| $5$ | $20$ | $10^6$ | / |
特殊性质 A：$w_i>0$