今、あなたは単純なゲームをプレイしています。長さ $n$ の配列 $A$ が与えられ、あなたのタスクは配列内でロボットを移動させるか停止させるかを制御することです。

初期状態では、ロボットの位置はランダムに選択されます。位置 $i \in [1, n]$ が選択される確率は $\frac{1}{n}$ です。各ターンにおいて、あなたは現在の位置を知っており、以下の2つの選択肢から行動を決定する必要があります。

• 停止 (Stop): この行動を選択すると、ゲームは直ちに終了します。ロボットが位置 $i$ で停止したとき、あなたのスコアは $A_i$ となります。
• 移動 (Move): この行動を選択し、ロボットが位置 $i$ にいる場合、50%の確率でロボットは $i - 1$ に移動し、残りの50%の確率で $i + 1$ に移動します。ロボットが位置 $1$ または $n$ にいるときは、この行動を選択できないことに注意してください。

2番目の行動はロボットが配列の両端にいない場合にのみ選択できるため、どのような戦略をとっても $\lim_{m \to +\infty} f(m) = 0$ となることが証明できます。ここで $f(m)$ は $m$ ターン経過後もゲームが続いている確率を表します。

あなたのタスクは、ゲームの期待スコアを最大化することです。

入力

1行目には整数 $n$ ($1 \le n \le 5 \cdot 10^5$) が与えられます。 2行目には $n$ 個の整数 $A_1, A_2, \dots, A_n$ ($1 \le A_i \le 10^{12}$) が与えられます。

出力

最大期待スコアを $998\,244\,353$ を法とする分数として1行で出力してください。 言い換えると、答えは $P/Q$ という有理数で表すことができ、$Q$ は $998\,244\,353$ と互いに素であることが証明できます。そのため、$(P \cdot Q^{-1}) \pmod{998\,244\,353}$ を出力する必要があります。

入出力例

入力 1

3
3 1 2

出力 1

499122179

入力 2

6
6 1 2 5 3 4

出力 2

582309211