题目描述

给定一个 $N$ 个整数的序列 $A$。对于序列 $A$，存在 $2^N - 1$ 个非空子序列 $B$。求所有子序列 $B$ 中的 $\\max\\left(B\\right) \\times \\min\\left(B\\right)$ 的和。

由于答案可能非常大，需要对 $998244353$ 取模后输出。

约束条件

• 输入中的所有值均为整数。
• $1 \leq N \leq 2 \times 10^5$
• $0 \leq A_i \leq 998244352$

输入

输入以以下格式从标准输入给出：

$N$ $A_1$ $A_2$ $\\cdots$ $A_N$

输出

输出答案。

示例输入 1

3
2 4 3

示例输出 1

63

共有 $7$ 个子序列 $B$，如下所示：

• $B = \\left(2\\right)$ ：$\\max\\left(B\\right) \\times \\min\\left(B\\right) = 4$
• $B = \\left(4\\right)$ ：$\\max\\left(B\\right) \\times \\min\\left(B\\right) = 16$
• $B = \\left(3\\right)$ ：$\\max\\left(B\\right) \\times \\min\\left(B\\right) = 9$
• $B = \\left(2, 4\\right)$ ：$\\max\\left(B\\right) \\times \\min\\left(B\\right) = 8$
• $B = \\left(2, 3\\right)$ ：$\\max\\left(B\\right) \\times \\min\\left(B\\right) = 6$
• $B = \\left(4, 3\\right)$ ：$\\max\\left(B\\right) \\times \\min\\left(B\\right) = 12$
• $B = \\left(2, 4, 3\\right)$ ：$\\max\\left(B\\right) \\times \\min\\left(B\\right) = 8$

答案为它们的和：$63$。

示例输入 2

1
10

示例输出 2

100

示例输入 3

7
853983 14095 543053 143209 4324 524361 45154

示例输出 3

206521341