102346: [AtCoder]ABC234 G - Divide a Sequence

Problem Statement

Given is a sequence $A$ of $N$ numbers.

There are $2^{N-1}$ ways to divide $A$ into non-empty contiguous subsequences $B_1,B_2,\ldots,B_k$. Find the value below for each of those ways, and print the sum, modulo $998244353$, of those values.

• $\prod_{i=1}^{k} (\max(B_i)-\min(B_i))$

Here, for a sequence $B_i=(B_{i,1},B_{i,2},\ldots,B_{i,j})$, $\max(B_i)$ and $\min(B_i)$ are defined to be the maximum and minimum values of an element of $B_i$, respectively.

Constraints

• $1 \leq N \leq 3 \times 10^5$
• $1 \leq A_i \leq 10^9$
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

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

Output

Print the sum, modulo $998244353$, of the values found.

Sample Input 1

3
1 2 3

Sample Output 1

2

There are $4$ ways to divide $A=(1,2,3)$ into non-empty contiguous subsequences, as follows.

• $(1)$, $(2)$, $(3)$
• $(1)$, $(2,3)$
• $(1,2)$, $(3)$
• $(1,2,3)$

$\prod_{i=1}^{k} (\max(B_i)-\min(B_i))$ for these divisions are $0$, $0$, $0$, $2$, respectively. The sum of them, $2$, should be printed.

Sample Input 2

4
1 10 1 10

Sample Output 2

90

Sample Input 3

10
699498050 759726383 769395239 707559733 72435093 537050110 880264078 699299140 418322627 134917794

Sample Output 3

877646588

Be sure to print the sum modulo $998244353$.

问题描述

给定一个包含$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$取模后的结果。

样例输入1

3
1 2 3

样例输出1

2

有$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$。它们的和$2$应该被打印出来。

样例输入2

4
1 10 1 10

样例输出2

90

样例输入3

10
699498050 759726383 769395239 707559733 72435093 537050110 880264078 699299140 418322627 134917794

样例输出3

877646588

确保打印的和对$998244353$取模。