Game

You are playing a simple game. Given an array $A$ of length $n$, you must control a robot that moves or stops within this array.

Initially, the robot's position is chosen at random: the probability that position $i \in [1, n]$ is selected is $\frac{1}{n}$. On each turn you know the current position, and you must decide between two actions.

• Stop. If you choose this action, the game ends immediately. When the robot stops at position $i$, your score is $A_i$.
• Move. If you choose this action and the robot is at position $i$, then with probability $50\%$ it moves to $i - 1$ and with probability $50\%$ it moves to $i + 1$. When the robot is at position $1$ or $n$, you cannot choose this action.

The second action can be chosen only when the robot is not at either end of the array, so for any strategy we can prove that $\lim\limits_{m \rightarrow +\infty} f(m) = 0$, where $f(m)$ is the probability that the game is still going 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 the maximum possible expected score as a fraction modulo $998\,244\,353$. In other words, 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$.