21100번 - Game 다국어

Now, you are playing a simple game. Given an array $A$ of length $n$, your task is to control a robot to move or stop in this array.

Initially, the position of the robot is randomly selected: the probability for selecting position $i \in [1, n]$ is $\frac{1}{n}$. In each turn, you know the current position, and need to make a decision between two action choices:

• Stop. If this action is selected, the game ends immediately. When the robot stops at position $i$, your score is $A_i$.
• Move. If this action is selected and the robot is at position $i$, with a $50\%$ chance, the robot will move to $i - 1$, and with another $50\%$ chance, it will move to $i + 1$. Note that when the robot is at position $1$ or $n$, you cannot select this action.

Since the second action can be selected only when the robot is not at either end of the array, we can prove that, for any strategy, $\lim\limits_{m \rightarrow +\infty} f(m) = 0$, where $f(m)$ represents the probability that the game continues after $m$ turns.

Your task is to maximize the expected score of the game.

The first line contains a single integer $n$ ($1 \le n \le 5 \cdot 10^5$).

The second line contains $n$ integers $A_1, A_2, \ldots, A_n$ ($1 \le A_i \le 10^{12}$).

Output a single line with a single integer: the maximum possible expected score as a fraction modulo $998\,244\,353$. In other words, it can be proven that the answer can be expressed as a rational number $P / Q$ where $Q$ is coprime with $998\,244\,353$, and you must output $(P \cdot Q^{-1}) \bmod 998\,244\,353$.