005 - Sum of Max of Sum and Product 2

問題文

　正整数 $N$ および正整数列 $A = (A_1,A_2,\cdots,A_N)$ が与えられます。以下の値を $998244353$ で割った余りを求めてください。 $$ \sum_{i = 1}^{N} \sum_{j = i}^N \max\left( \sum_{k=i}^{j} A_k, \prod_{k=i}^{j} A_k \right) $$

制約

• $1 \le N \le 2 \times 10^5$
• $1 \le A_i \le 10^9$
• 入力はすべて整数である

入出力

入力

入力は以下の形式で標準入力から与えられる。

N
A_1 A_2 ... A_N

出力

計算結果を出力せよ。

サンプル

入力例 1

3
1 2 3

出力例 1

21

入力例 2

6
3 1 4 1 5 9

出力例 2

1163

提出

提出はこちらから行えます。