子序列最值乘积之和

时间限制：2s
空间限制：512MB

题目描述

给定一个长度为 $N$ 的整数序列 $A$。$A$ 的非空子序列 $B$ 一共有 $2^N-1$ 个。对于每一个 $B$，计算 $\max(B)\times\min(B)$，并求这些值的总和。

由于答案可能很大，请输出其对 $998244353$ 取模的结果。

输入格式

第一行一个整数 $N$。

第二行 $N$ 个整数 $A_1,A_2,\ldots,A_N$。

输出格式

输出一个整数，表示答案对 $998244353$ 取模的结果。

样例输入 1

3
2 4 3

样例输出 1

63

样例输入 2

1
10

样例输出 2

100

样例输入 3

7
853983 14095 543053 143209 4324 524361 45154

样例输出 3

206521341

样例解释 1

七个非空子序列对应的乘积依次为 $4,16,9,8,6,12,8$，总和为 $63$。

数据范围

• $1\le N\le 2\times 10^5$；
• $0\le A_i\le 998244352$；
• 输入均为整数。