题目描述

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

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

输入格式

输入以如下格式从标准输入给出。

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

输出格式

输出答案。

样例 1

输入

3
2 4 3

输出

63

样例 2

输入

1
10

输出

100

样例 3

输入

7
853983 14095 543053 143209 4324 524361 45154

输出

206521341

说明/提示

限制条件

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

样例解释 1

$B$ 可以为以下 $7$ 个：

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

上述 $7$ 个值的和为 $63$，即为答案。

由 ChatGPT 4.1 翻译