Description

Bob 正在数轴上玩一个单人游戏。

数轴上有 $n$ 个点。每次，玩家选择两个点。这两个点将被移除，并添加它们的中点。当数轴上只剩下一个点时，游戏结束。形式上，如果选择的两个点是 $x_i$ 和 $x_j$，那么在操作后将添加 $\dfrac{x_i+x_j}{2}$。

为了愉快地玩这个游戏，Bob 总是随机选择两个相邻的点。最初，第 $i$ 个点和第 $(i+1)$ 个点是相邻的。当 Bob 添加一个新点时，它继承其左点的左相邻点和其右点的右相邻点。

现在 Bob 有一个问题：最后一个点的期望位置在哪里。

可以证明，答案可以表示为 $\dfrac{p}{q}$ 的形式，你只需要输出 $p\cdot q^{-1} \bmod 998\,244\,353$ 的值。

Input Format

第一行包含一个整数 $n$ ($1 \le n \le 10^6$)。

第二行包含 $n$ 个整数 $x_i$ ($0 \le x_1 \le \dots \le x_n < 998\,244\,353$)，描述第 $i$ 个点的位置。

注意，两个点可能在同一位置。

Output Format

输出一个整数，即答案对 $998\,244\,353$ 取模的结果。

3
1 2 4

623902723

Hint

（由 ChatGPT 4o 翻译）