B - Products of Min-Max Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 400 点

問題文

長さ N の整数列 A が与えられます。A の空でない部分列 B は 2^N - 1 個あります。これらについて \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

B として、以下の 7 つが考えられます。

  • 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

以上の 7 つの値を足した値 63 が答えです。

入力例 2

1
10

出力例 2

100

入力例 3

7
853983 14095 543053 143209 4324 524361 45154

出力例 3

206521341

Score : 400 points

Problem Statement

Given is a sequence A of N integers. There are 2^N - 1 non-empty subsequences B of A. Find the sum of \max\left(B\right) \times \min\left(B\right) over all of them.

Since the answer can be enormous, report it modulo 998244353.

Constraints

  • All values in input are integers.
  • 1 \leq N \leq 2 \times 10^5
  • 0 \leq A_i \leq 998244352

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 \cdots A_N

Output

Print the answer.

Sample Input 1

3
2 4 3

Sample Output 1

63

There are 7 subsequences B, as follows:

  • 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

The answer is the sum of them: 63.

Sample Input 2

1
10

Sample Output 2

100

Sample Input 3

7
853983 14095 543053 143209 4324 524361 45154

Sample Output 3

206521341