AT_abc234_g.[ABC234G] Divide a Sequence

给定一个长度为 $N$ 的数列 $A$。

将 $A$ 切分为若干个非空、连续的子序列 $B_1,B_2,\ldots,B_k$ 的方法共有 $2^{N-1}$ 种。对于每一种切分方式，计算如下的值，并将所有切分方式下的结果求和后对 $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)$ 表示 $B_i$ 中元素的最大值，$\min(B_i)$ 表示 $B_i$ 中元素的最小值。

输入以如下格式从标准输入读入：

$N$ $A_1$ $A_2$ $\ldots$ $A_N$

输出所求值的总和对 $998244353$ 取模后的结果。

数据范围

• $1\leq N\leq 3\times 10^5$
• $1\leq A_i\leq 10^9$
• 输入均为整数

样例解释 1

将 $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$，输出 $2$。

样例解释 3

请注意，输出时需要对 $998244353$ 取模。

由 ChatGPT 4.1 翻译