题面翻译

给出一个由 $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$ 中元素的最大值和最小值。

输入格式

第一行输入一个整数 $N$

第二行输入 $N$ 个空格隔开的整数 $A_1,A_2,\cdots,A_N$

输出格式

输出一个整数

3
1 2 3

2

4
1 10 1 10

90

10
699498050 759726383 769395239 707559733 72435093 537050110 880264078 699299140 418322627 134917794

877646588

提示

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

Sample Explanation 1

有 $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$ 。它们的总和是 $0+0+0+2=2$ 。