题目描述

给定一个由 $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$ 中的最小值。

约束条件

• $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

将 $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

4
1 10 1 10

示例输出 2

90

示例输入 3

10
699498050 759726383 769395239 707559733 72435093 537050110 880264078 699299140 418322627 134917794

示例输出 3

877646588

请确保将计算结果对 $998244353$ 取模后输出。