配点 : $600$ 点

問題文

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

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$ で割ったあまりを出力することに注意してください。