划分序列

题目描述

给定一个由 $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)$ 和 $\min(B_i)$ 分别定义为 $B_i$ 中元素的最大值和最小值。

输入格式

输入按以下格式从标准输入给出：

$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$ 取模后输出。

数据范围

• $1 \le N \le 3 \times 10^5$
• $1 \le A_i \le 10^9$
• 输入中的所有值均为整数。