CF2264C.Madamant's Skating Dynasty

Madam Madamant is expecting a baby and already planning a skating dynasty in which every parent is a stronger skater than their children.

Formally, Madamant has $n$ labeled skaters. Skater $v$ has an integer rating $a_v$, and all ratings are pairwise distinct. A possible dynasty is represented by a rooted tree on these skaters.

Let $r$ be the root of the tree. For every skater $v \ne r$, let $p_v$ be the parent of $v$. The dynasty is valid if $a_v \lt a_{p_v}$ for every $v \ne r$.

The cost of a valid dynasty is $$ \sum_{v \ne r} (a_{p_v} - a_v). $$

Two dynasties are different if their roots are different or if the parent of at least one skater is different.

Find the sum of the costs of all valid dynasties Madamant can form, modulo $998\,244\,353$.

玛丹夫人即将迎来宝宝，并已开始规划一个滑冰王朝，其中每位父母的滑冰水平都强于其子女。

形式化地，玛丹夫人有 $n$ 位编号的滑冰者。滑冰者 $v$ 具有一个整数评分 $a_v$，且所有评分两两互异。一个可能的王朝由这些滑冰者构成的一棵有根树表示。

设 $r$ 为该树的根节点。对每个滑冰者 $v \ne r$，令 $p_v$ 表示 $v$ 的父节点。若对每个 $v \ne r$ 均满足 $a_v \lt a_{p_v}$，则该王朝是合法的。

一个合法王朝的代价定义为

$$\sum_{v \ne r} (a_{p_v} - a_v).$$

若两棵王朝树的根节点不同，或至少存在一位滑冰者的父节点不同，则认为这两棵王朝树不同。

求玛丹夫人所能构造的所有合法王朝的代价之和，对 $998\,244\,353$ 取模的结果。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of skaters.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^9$) — their ratings.

It is guaranteed that all $a_i$ are pairwise distinct.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$）——滑冰者的数量。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le 10^9$）——他们的评分。

保证所有 $a_i$ 两两不同。

保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。

For each test case, print one integer — the sum of the costs of all valid dynasties, modulo $998\,244\,353$.

对于每个测试用例，输出一个整数——所有合法王朝的代价之和对 $998\,244\,353$ 取模的结果。

In the second test case, the skater with rating $3$ must be the root. The parent of the skater with rating $2$ must be the skater with rating $3$, while the skater with rating $1$ can choose either of the other skaters as their parent. The two valid dynasties have costs $2$ and $3$, so the answer is $5$.

In the fourth test case, there is only one valid dynasty. Its cost is $10^9 - 1 = 999\,999\,999$, whose remainder modulo $998\,244\,353$ is $1\,755\,646$.

在第二个测试用例中，评分为 $3$ 的滑冰者必须为根节点。评分为 $2$ 的滑冰者的父节点必须是评分为 $3$ 的滑冰者，而评分为 $1$ 的滑冰者则可任选其余两名滑冰者之一作为其父节点。两种合法的家族树（dynasty）的成本分别为 $2$ 和 $3$，因此答案为 $5$。

在第四个测试用例中，仅存在一种合法的家族树。其成本为 $10^9 - 1 = 999\,999\,999$，该值对 $998\,244\,353$ 取模的余数为 $1\,755\,646$。