U183887 山区建小学期望版

数轴上有 $n$ 个人，坐标为 $x[1...n]$。首先选出所有村庄的一个子集 $S$，接着可以在数轴上任意一点建一所小学，求出子集中所有人上学的最小总距离 $res$。若 $S$ 为空集，约定 $res=0$。 现在，假设子集 $S$ 是随机选取的（$2^n$ 种情况等概率发生），对于每种情况互不影响（即可以独立决策小学的位置）。请你计算 $res$ 的期望，对 998244353 取模。

第一行1个整数 $n$ 第二行 $n$ 个整数 $x[i]$

输出一个整数，代表答案

【样例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$ 【数据范围】 对于 20% 的数据，$n \le 10$ 对于 50% 的数据，$n \le 100$ 对于 90% 的数据，$n\le 3000$ 对于 100% 的数据，$1\le n\le 10^6, 1\le x[i] \le 10^9$，保证 $x[i] \le x[i+1]$。