题解

题目描述

给定一个长度为 $n$ 的数组 $a$，需要将其划分为三个非空的连续子数组
$[1,x],\quad[x+1,y],\quad[y+1,n]$
使得三段和的乘积
最大化。输出最大值对 $998244353$ 取模的结果。

题目内容

$Tk$ 有一个长度为$n$的数组$a$，他希望将数组分割为$[1,x_1],[x_1+1,x_2],[x_2+1,n]$三个部分并使 $\sum^{x_1}_{i=1}$$\sum^{x_2}_{j={x_1}+1}$$\sum^n_{k=x_2+1}$$a_i×a_j×a_k$最大,这却难到聪明的他了，现在他来寻求你的帮助，不过你并不需要告诉他具体分割位置，只需要告诉他最终结果即可，并将最终结果对$998244353$求余。

输入描述

第一行输入一个正整数$n(3 ≦n ≦ 2×10^5)$表示数组大小，接下来输入$n$个整数 $a_i(1 ≦ a_i≦2×10^5)$表示数组第$i$个数的值。

输出描述

输出一个值表示最终结果。

样例1

输入

5
3 2 4 1 5

输出

125

说明

分割最终区间为$[1,2]，[3,4]，[5]$可以得到最大值$125$。