問題文

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