题目描述

長さ $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$ で割ったあまりを出力せよ。

题目大意

给定长度为 $N$ 的序列 $A$，我们定义一种将 $A$ 划分为若干段的方案的价值为每一段的最大值减去最小值的差的乘积，你需要求出所有划分方案的价值的总和，答案对 $998244353$ 取模。

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

$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$ を出力します。

Sample Explanation 3

$998244353$ で割ったあまりを出力することに注意してください。