Gramy w prostą grę. Dana jest tablica $A$ o długości $n$, a Twoim zadaniem jest sterowanie robotem, który może się poruszać lub zatrzymać w tej tablicy.

Początkowo pozycja robota jest wybierana losowo: prawdopodobieństwo wybrania pozycji $i \in [1, n]$ wynosi $\frac{1}{n}$. W każdej turze znasz aktualną pozycję i musisz podjąć decyzję między dwoma możliwymi akcjami:

• Stop. Jeśli wybierzesz tę akcję, gra kończy się natychmiast. Gdy robot zatrzyma się na pozycji $i$, Twój wynik wynosi $A_i$.
• Move. Jeśli wybierzesz tę akcję, a robot znajduje się na pozycji $i$, to z prawdopodobieństwem 50% robot przesunie się na pozycję $i - 1$, a z prawdopodobieństwem 50% przesunie się na pozycję $i + 1$. Zauważ, że gdy robot znajduje się na pozycji $1$ lub $n$, nie możesz wybrać tej akcji.

Ponieważ drugą akcję można wybrać tylko wtedy, gdy robot nie znajduje się na żadnym z końców tablicy, można udowodnić, że dla dowolnej strategii $\lim_{m \to +\infty} f(m) = 0$, gdzie $f(m)$ reprezentuje prawdopodobieństwo, że gra trwa po $m$ turach.

Twoim zadaniem jest zmaksymalizowanie oczekiwanego wyniku gry.

Wejście

Pierwsza linia zawiera pojedynczą liczbę całkowitą $n$ ($1 \le n \le 5 \cdot 10^5$). Druga linia zawiera $n$ liczb całkowitych $A_1, A_2, \dots, A_n$ ($1 \le A_i \le 10^{12}$).

Wyjście

Wypisz w jednej linii pojedynczą liczbę całkowitą: maksymalny możliwy oczekiwany wynik jako ułamek modulo $998\,244\,353$. Innymi słowy, można udowodnić, że wynik można wyrazić jako liczbę wymierną $P/Q$, gdzie $Q$ jest względnie pierwsze z $998\,244\,353$, a Ty musisz wypisać $(P \cdot Q^{-1}) \pmod{998\,244\,353}$.

Przykład

Wejście 1

3
3 1 2

Wyjście 1

499122179

Wejście 2

6
6 1 2 5 3 4

Wyjście 2

582309211