← 返回题目列表

AtCoder · arc116_b

B. 最小-最大乘积

中文机器翻译题面 查看原题

分数: 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