現在，你正在玩一個簡單的遊戲。給定一個長度為 $n$ 的陣列 $A$，你的任務是控制一個機器人在這個陣列中移動或停止。

最初，機器人的位置是隨機選擇的：選擇位置 $i \in [1, n]$ 的機率為 $\frac{1}{n}$。在每一回合中，你知道當前的位置，並需要在兩個動作選擇之間做出決定：

• 停止 (Stop)。如果選擇此動作，遊戲立即結束。當機器人在位置 $i$ 停止時，你的得分為 $A_i$。
• 移動 (Move)。如果選擇此動作且機器人在位置 $i$，機器將有 50% 的機率移動到 $i - 1$，並有 50% 的機率移動到 $i + 1$。請注意，當機器人在位置 $1$ 或 $n$ 時，你不能選擇此動作。

由於第二個動作只有在機器人不在陣列兩端時才能選擇，我們可以證明，對於任何策略，$\lim_{m \to +\infty} f(m) = 0$，其中 $f(m)$ 代表遊戲在 $m$ 回合後仍繼續進行的機率。

你的任務是最大化遊戲的期望得分。

輸入格式

第一行包含一個整數 $n$ ($1 \le n \le 5 \cdot 10^5$)。 第二行包含 $n$ 個整數 $A_1, A_2, \dots, A_n$ ($1 \le A_i \le 10^{12}$)。

輸出格式

輸出單行一個整數：最大可能的期望得分，以模 $998\,244\,353$ 的分數形式表示。 換句話說，可以證明答案可以表示為有理數 $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