当前没有测试数据。

G - 划分序列

得分：$600$ 点

问题描述

给定一个由 $N$ 个数字组成的序列 $A$。

有 $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$ 取模后的结果。

3
1 2 3

2

将 $A=(1,2,3)$ 划分为非空的连续子序列共有 $4$ 种方式，如下所示。

• $(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$，应当输出。

4
1 10 1 10

90

10
699498050 759726383 769395239 707559733 72435093 537050110 880264078 699299140 418322627 134917794

877646588

注意要对和取模 $998244353$ 后输出。