← 返回题目列表

AtCoder · abc234_g

G. 划分序列

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

分数: 600 点

问题陈述

给定的是一个序列 A of N 数字。

有 2^{N-1} 划分方法 A 变为非空 连续 子序列 B_1,B_2,\ldots,B_k。为每种方式找到下面的值,并打印总和,模 998244353,这些值。

  • \prod_{i=1}^{k} (\max(B_i)-\min(B_i))

这里,对于一个序列 B_i=(B_{i,1},B_{i,2},\ldots,B_{i,j}), \max(B_i) 和 \min(B_i) 被定义为元素的最大值和最小值 B_i。

约束

  • 1 \leq N \leq 3 \times 10^5
  • 1 \leq A_i \leq 10^9
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

N
A_1 A_2 \ldots A_N

输出

打印总和,模数 998244353,找到的值。


示例输入 1

3
1 2 3

示例输出 1

2

有 4 划分方法 A=(1,2,3) 转换为非空连续子序列,如下所示。

  • (1), (2), (3)
  • (1), (2,3)
  • (1,2), (3)
  • (1,2,3)

\prod_{i=1}^{k} (\max(B_i)-\min(B_i)) 这些部门是 分别是 0, 0, 0, 2。他们的总和, 2,应打印。


示例输入 2

4
1 10 1 10

示例输出 2

90

示例输入 3

10
699498050 759726383 769395239 707559733 72435093 537050110 880264078 699299140 418322627 134917794

示例输出 3

877646588

请务必打印模数总和 998244353.