Vous jouez à un jeu simple. Étant donné un tableau $A$ de longueur $n$, votre tâche consiste à contrôler un robot pour qu'il se déplace ou s'arrête dans ce tableau.

Initialement, la position du robot est choisie aléatoirement : la probabilité de choisir la position $i \in [1, n]$ est $\frac{1}{n}$. À chaque tour, vous connaissez la position actuelle et devez prendre une décision entre deux choix d'action :

• Stop. Si cette action est sélectionnée, le jeu se termine immédiatement. Lorsque le robot s'arrête à la position $i$, votre score est $A_i$.
• Move. Si cette action est sélectionnée et que le robot est à la position $i$, avec 50 % de chance, le robot se déplacera vers $i - 1$, et avec 50 % de chance, il se déplacera vers $i + 1$. Notez que lorsque le robot est à la position $1$ ou $n$, vous ne pouvez pas sélectionner cette action.

Puisque la seconde action ne peut être sélectionnée que lorsque le robot n'est pas à l'une des extrémités du tableau, nous pouvons prouver que, pour toute stratégie, $\lim_{m \to +\infty} f(m) = 0$, où $f(m)$ représente la probabilité que le jeu continue après $m$ tours.

Votre tâche est de maximiser l'espérance du score du jeu.

Entrée

La première ligne contient un entier unique $n$ ($1 \le n \le 5 \cdot 10^5$). La seconde ligne contient $n$ entiers $A_1, A_2, \dots, A_n$ ($1 \le A_i \le 10^{12}$).

Sortie

Affichez une seule ligne avec un entier unique : le score espéré maximum possible sous forme de fraction modulo $998\,244\,353$. En d'autres termes, il peut être prouvé que la réponse peut être exprimée sous la forme d'un nombre rationnel $P/Q$ où $Q$ est premier avec $998\,244\,353$, et vous devez afficher $(P \cdot Q^{-1}) \pmod{998\,244\,353}$.

Exemples

Entrée 1

3
3 1 2

Sortie 1

499122179

Entrée 2

6
6 1 2 5 3 4

Sortie 2

582309211