题目描述

菜菜的 Jayce 认为自己很水，事实上确实是这样的。

有 $n$ 位神仙，第 $i$ 位的神仙度为 $a_i$。Jayce 打算选择一个区间 $[l, r](1 \le l \le r \le n)$，并吸收这段区间大佬的神仙度。

具体的，神仙度会从高浓度扩散到低浓度。Jayce 一开始的神仙度是 $s = 0$，每次 Jayce 可以选择一个区间中的神仙 $i \in [l, r]$，并疯狂膜拜该神仙，令 $s$ 和 $a_i$ 都变为原先两者的平均值，即 $\frac {s+a_i} 2$。Jayce 可以进行至多 $LIM=114514^{1919810}$ 次膜拜操作，定义区间 $[l, r]$ 的神仙度是：Jayce 通过至多 $LIM$ 次膜拜操作能得到的最大 $s$（初始 $s = 0$）。

Jayce 想知道所有 $\frac {n(n+1)}{2}$ 个区间的神仙度之和对 $998244353$ 取模后的值。

输入格式

第一行一个正整数 $n$，表示神仙的数量。

第二行 $n$ 个正整数 $a_i$，表示每个神仙的神仙度。

输出格式

输出一个数表示答案。

样例

样例 1

3
1 2 3

623902729

取模前答案为 $\frac {67} 8$。

样例 2

6
1 1 4 5 1 4

889061433

样例 3

18
9 9 8 2 4 4 3 5 3 9 9 3 2 4 4 8 5 3

681808275

子任务

对于 $100\%$ 的数据，满足 $1\le n\le 5\times 10^5$，$1\le a_i\le 10^9$。

• 子任务 $1$（$10$ 分）：$n\le 10$。
• 子任务 $2$（$20$ 分）：$n\le 100$，依赖子任务 $1$。
• 子任务 $3$（$20$ 分）：$n\le 5\times 10^3$，依赖子任务 $1,2$。
• 子任务 $4$（$20$ 分）：$n\le 10^5$，依赖子任务 $1,2,3$。
• 子任务 $5$（$20$ 分）：$a_i\le 100$。
• 子任务 $6$（$10$ 分）：无特殊限制，依赖子任务 $1,2,3,4,5$。