問題文

箱星さんはヤング図形が大好きです。

広義単調減少列 $A=(A_1,A_2,\ldots,A_N)$ のヤング図形を考えます。すなわち、上から $i$ 行目に $A_i$ 個の正方形を左詰めで並べます。

ヤング図形のマスに下向きまたは右向きのカメラを設置します。あるマスに下向きのカメラを設置すると、そのマス自身とそのマスより下のマスが監視されます。あるマスに右向きのカメラを設置すると、そのマス自身とそのマスより右のマスが監視されます。

次の条件をすべて満たすようにカメラを設置する方法の数を $998244353$ で割った余りを求めてください。

• 各マスについて、そのマスにあるカメラの個数は $0$ 個または $1$ 個である。
• どのマスもあるカメラによって監視される。
• カメラの存在するマスは他のカメラによって監視されない。

制約

• $1\le N\le 10^5$
• $1\le A_i\le 10^5$
• $A_1\ge A_2\ge\cdots\ge A_N$
• 入力はすべて整数

$N$
$A_1$ $A_2$ $\cdots$ $A_N$

サンプル

サンプル1

入力サンプルをコピー

入力

2
3 2

出力

7

サンプル2

入力サンプルをコピー

入力

3
111 22 3

出力

375

サンプル3

入力サンプルをコピー

入力

6
3 2 2 1 1 1

出力

14