AT_arc231_e.Odd Inversion

You are given a sequence of positive integers $A = (A_1, A_2, \cdots, A_N)$ of length $N$. Here, $A_1 \leq A_2 \leq \cdots \leq A_N$ holds.

Find the number, modulo $998\,244\,353$, of possible sequences of positive integers $B$ of length $N$ satisfying the following conditions.

• $1 \leq B_i \leq A_i$ ($1 \leq i \leq N$)
• The inversion number of $B$ is odd.

Here, the inversion number of $B$ is the number of pairs of integers $(i, j)$ satisfying $1 \leq i < j \leq N$ such that $B_i > B_j$.

Solve $T$ test cases per input file.

给你一个长度为 $N$ 的正整数序列 $A = (A_1, A_2, \cdots, A_N)$，满足 $A_1 \leq A_2 \leq \cdots \leq A_N$。

求满足以下条件的长度为 $N$ 的正整数序列 $B$ 的个数（对 $998\,244\,353$ 取模）：

• $1 \leq B_i \leq A_i$（$1 \leq i \leq N$）；
• $B$ 的逆序数为奇数。

其中，$B$ 的逆序数定义为满足 $1 \leq i < j \leq N$ 且 $B_i > B_j$ 的整数对 $(i, j)$ 的个数。

每组输入文件需处理 $T$ 组测试用例。

The input is given from Standard Input in the following format. Here, $\mathrm{case}_i$ ($1 \leq i \leq T$) denotes the $i$-th test case.

$T$
$\mathrm{case}_1$
$\mathrm{case}_2$
$\vdots$
$\mathrm{case}_T$

Each test case is given in the following format:

$N$
$A_1$ $A_2$ $\cdots$ $A_N$

输入从标准输入中按以下格式给出。其中，$\mathrm{case}_i$（$1 \leq i \leq T$）表示第 $i$ 个测试用例。

$T$
$\mathrm{case}_1$
$\mathrm{case}_2$
$\vdots$
$\mathrm{case}_T$

每个测试用例按以下格式给出：

$N$
$A_1$ $A_2$ $\cdots$ $A_N$

Output $T$ lines. The $i$-th line ($1 \leq i \leq T$) should contain the answer for $\mathrm{case}_i$.

输出 $T$ 行。第 $i$ 行（$1 \leq i \leq T$）应包含 $\mathrm{case}_i$ 的答案。

Sample 1 Explanation:

• For the first test case, $(2, 1)$ satisfies the conditions.
• For the second test case, $(1, 2, 1), (2, 1, 2), (2, 1, 3)$ satisfy the conditions.

Constraints

• $1 \leq T \leq 10\,000$
• $1 \leq N \leq 200\,000$
• $1 \leq A_1 \leq A_2 \leq \cdots \leq A_N \leq 10^9$
• The sum of $N$ over the $T$ test cases is at most $400\,000$.
• All input values are integers.

样例 1 解释：

• 对于第一个测试用例，$(2, 1)$ 满足条件。
• 对于第二个测试用例，$(1, 2, 1)$、$(2, 1, 2)$、$(2, 1, 3)$ 满足条件。

约束条件

• $1 \leq T \leq 10\,000$
• $1 \leq N \leq 200\,000$
• $1 \leq A_1 \leq A_2 \leq \cdots \leq A_N \leq 10^9$
• 所有 $T$ 个测试用例的 $N$ 值之和不超过 $400\,000$。
• 所有输入值均为整数。