Ahora, estás jugando un juego simple. Dado un arreglo $A$ de longitud $n$, tu tarea es controlar a un robot para que se mueva o se detenga en este arreglo.

Inicialmente, la posición del robot se selecciona al azar: la probabilidad de seleccionar la posición $i \in [1, n]$ es $\frac{1}{n}$. En cada turno, conoces la posición actual y debes tomar una decisión entre dos opciones de acción:

• Detenerse (Stop). Si se selecciona esta acción, el juego termina inmediatamente. Cuando el robot se detiene en la posición $i$, tu puntuación es $A_i$.
• Moverse (Move). Si se selecciona esta acción y el robot está en la posición $i$, con un 50% de probabilidad el robot se moverá a $i - 1$, y con otro 50% de probabilidad se moverá a $i + 1$. Ten en cuenta que cuando el robot está en la posición 1 o $n$, no puedes seleccionar esta acción.

Dado que la segunda acción solo puede seleccionarse cuando el robot no está en ninguno de los extremos del arreglo, podemos probar que, para cualquier estrategia, $\lim_{m \to +\infty} f(m) = 0$, donde $f(m)$ representa la probabilidad de que el juego continúe después de $m$ turnos.

Tu tarea es maximizar la puntuación esperada del juego.

Entrada

La primera línea contiene un único entero $n$ ($1 \le n \le 5 \cdot 10^5$).

La segunda línea contiene $n$ enteros $A_1, A_2, \dots, A_n$ ($1 \le A_i \le 10^{12}$).

Salida

Imprime una sola línea con un único entero: la máxima puntuación esperada posible como una fracción módulo 998 244 353. En otras palabras, se puede demostrar que la respuesta puede expresarse como un número racional $P/Q$ donde $Q$ es coprimo con 998 244 353, y debes imprimir $(P \cdot Q^{-1}) \pmod{998 244 353}$.

Ejemplos

Entrada 1

3
3 1 2

Salida 1

499122179

Entrada 2

6
6 1 2 5 3 4

Salida 2

582309211