题解

题目描述

给定一个长度为 $n$ 的数组 ${a_1,a_2,\dots,a_n}$，需要将数组分成两部分：前缀部分 ${a_1,a_2,\dots,a_x}$ 和后缀部分 ${a_{x+1},a_{x+2},\dots,a_{n}}$（其中 $1 \le x < n$），使得下式达到最大值：

$sum_{i=1}^{x} \sum_{j=x+1}^{n} a_i \times a_j$

注意：输出结果需对$998244353$ 取模。

题目内容

$Tk$有一个长度为$n$的数组{$a_1,a_2,...,a_n$}，他希望将数组分割为{$a_1,a_2,...,a_x$}和{$a_{x+1},a_{x+2},a_n$}两个部分(显然，$x$需要满足$1 ≦x<n$)，使得下式的答案达到最大:

$\sum^x_{i=1}\sum^n_{j=x+1}a_i×a_j$

这却难倒聪明的他了，现在他来寻求你的帮助，不过你并不需要告诉他具体分割位置，只需要告诉他最终结果即可。由于答案可能很大，请将答案对 $998\ 244\ 353$取模后输出。

输入描述

第一行输入一个正整数$n(2≦n≦2×10^5)$表示数组大小。

第二行输入$n$个整数$a_1,a_2,...,a_n (1≦a≦10^4)$代表数组中的元素。

输出描述

输出一个值表示上式的最大值。由于答案可能很大，请将答案对$998\ 244\ 353$取模后输出。

样例1

输入

5
3 2 4 1 5

输出

54

说明

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