题目背景

题目描述

令一个长度为 $p$ 的序列的权值为将这个序列按任意顺序重排后使得序列第一个数为最小值，可能的 $\sum\limits_{i=1}^{p-1}(a_{i+1}-a_i)^2$ 的最大值。

给定一个长度为 $n$ 序列，现在求这个序列所有长度为偶数的非空子序列（可以不连续）的权值和，结果对 $998244353$ 取模。

输入格式

共两行。

第一行，共一个正整数 $n$ 表示序列长度。
第二行，共 $n$ 个正整数表示序列 $a$。

输出格式

共一行，一个正整数表示答案，结果对 $998244353$ 取模。

4
1 2 3 4

34

提示

样例解释

对于样例一中的序列，共有以下几个子序列（长度为 $1$ 不计入）计入权值：

1. $\langle1,2\rangle$，贡献权值为 $1$；
2. $\langle1,3\rangle$，贡献权值为 $4$；
3. $\langle1,4\rangle$，贡献权值为 $9$；
4. $\langle2,3\rangle$，贡献权值为 $1$；
5. $\langle2,4\rangle$，贡献权值为 $4$；
6. $\langle3,4\rangle$，贡献权值为 $1$；
7. $\langle1,2,3,4\rangle$，贡献权值为 $9+4+1=14$。

所以总贡献为 $1+4+9+1+4+1+14=34$。

数据范围

本题采用捆绑测试。

对于 $100\%$ 的测试数据，满足 $2\le n \le 5\times10^3$，$1\le a_i\le 10^9$。