U183887 山区建小学期望版

数轴上有 $n$ 个人，第 $i$ 个人的坐标为 $x_i$，并保证 $$ x_1\le x_2\le\cdots\le x_n. $$ 从这 $n$ 个人中等概率地选择一个子集 $S$，也就是说 $2^n$ 个子集出现的概率都为 $2^{-n}$。 对于已经选出的子集，可以在数轴上的任意位置 $y$ 建一所小学。定义这个子集的最小总距离为 $$ res(S)=\min_y\sum_{i\in S}|x_i-y|. $$ 若 $S$ 是空集，约定 $res(S)=0$。 求 $res(S)$ 的期望，答案对 $998244353$ 取模。 “期望对模数取模”的含义是：先求所有子集的 $res(S)$ 之和，再乘以 $2^n$ 在模 $998244353$ 下的逆元。

第一行一个整数 $n$。 第二行 $n$ 个整数 $x_1,x_2,\ldots,x_n$。

输出一个整数，表示所求期望对 $998244353$ 取模后的结果。

## 样例解释 1. 总共8种情况： - $S = [], res = 0$ - $S = [1], res = 0$ - $S = [1,2], res = 1$ - $S = [1,3], res = 2$ - $S = [1,2,3], res = 2$ - $S = [2], res = 0$ - $S = [2,3], res = 1$ - $S = [3], res = 0$ 期望为 $(1+2+2+1)/8 = 3/4$ 2. 四个子集分别是 $\varnothing,\{1\},\{3\},\{1,3\}$，对应最小总距离为 $0,0,0,2$。期望为 $\dfrac24=\dfrac12$，模意义结果为 $499122177$。 ## 数据范围与子任务 对全部数据： $$ 1\le n\le10^6,\qquad 1\le x_i\le10^9,\qquad x_i\le x_{i+1}. $$ | 子任务 | 测试点数 | 分值 | 额外限制 | | -----: | -------: | ---: | ---------- | | 1 | 4 | 15 | $n\le10$ | | 2 | 5 | 10 | $n\le30$ | | 3 | 6 | 15 | $n\le100$ | | 4 | 7 | 18 | $n\le3000$ | | 5 | 8 | 22 | $n\le10^5$ | | 6 | 9 | 20 | 无额外限制 | 子任务独立计分。