Теперь вы играете в простую игру. Дан массив $A$ длины $n$, ваша задача — управлять роботом, который может перемещаться по этому массиву или остановиться.

Изначально позиция робота выбирается случайным образом: вероятность выбора позиции $i \in [1, n]$ равна $\frac{1}{n}$. На каждом ходу вы знаете текущую позицию и должны сделать выбор между двумя действиями:

• Stop (Остановиться). Если выбрано это действие, игра немедленно заканчивается. Когда робот останавливается в позиции $i$, ваш счет равен $A_i$.
• Move (Переместиться). Если выбрано это действие и робот находится в позиции $i$, то с вероятностью 50% робот переместится в $i - 1$, и с вероятностью 50% он переместится в $i + 1$. Заметьте, что если робот находится в позиции $1$ или $n$, вы не можете выбрать это действие.

Поскольку второе действие можно выбрать только тогда, когда робот не находится на одном из концов массива, можно доказать, что для любой стратегии $\lim_{m \to +\infty} f(m) = 0$, где $f(m)$ представляет вероятность того, что игра продолжается после $m$ ходов.

Ваша задача — максимизировать математическое ожидание счета в игре.

Входные данные

Первая строка содержит единственное целое число $n$ ($1 \le n \le 5 \cdot 10^5$). Вторая строка содержит $n$ целых чисел $A_1, A_2, \dots, A_n$ ($1 \le A_i \le 10^{12}$).

Выходные данные

Выведите одну строку с единственным целым числом: максимально возможное математическое ожидание счета как дробь по модулю $998\,244\,353$. Иными словами, можно доказать, что ответ может быть представлен в виде рационального числа $P/Q$, где $Q$ взаимно просто с $998\,244\,353$, и вы должны вывести $(P \cdot Q^{-1}) \pmod{998\,244\,353}$.

Примеры

1

3
3 1 2

1

499122179

2

6
6 1 2 5 3 4

2

582309211