题目内容

法师获得了一卷古老的魔法卷轴，上面依次排列着 $n$ 个符文，第 $i$ 个符文蕴含着正整数能量 $w_i$。他想将卷轴切成三段连续的非空片段，用来释放三种不同的法术。假设切割的位置为 $p$ 和 $q$（$1 \le p < q \le n-1$），三段符文的能量总和分别为 $S_1 = \sum_{i=1}^{p} w_i$，$S_2 = \sum_{i=p+1}^{q} w_i$，$S_3 = \sum_{i=q+1}^{n} w_i$。三种法术的总威力定义为 $S_1 \times S_2 \times S_3$。请问在最优的划分下，总威力最大可以是多少？由于答案可能很大，请输出它对 $998244353$ 取模的结果。

符文个数 $n$ 满足 $3 \le n \le 2 \times 10^5$。每个符文的能量值 $w_i$ 满足 $1 \le w_i \le 2 \times 10^5$。

输入描述

第一行包含一个整数 $n$ ($3 \le n \le 2 \times 10^5$)，表示符文个数。 第二行包含 $n$ 个整数 $w_1, w_2, \dots, w_n$ ($1 \le w_i \le 2 \times 10^5$)，依次表示每个符文的能量值。