分数: 400 点
问题陈述
给定的是一个序列 A of N 整数。有 2^N - 1 非空子序列 B of A。求总和 \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