CF1666F.Fancy Stack

Little Fiona has a collection of $n$ blocks of various sizes $a_1, a_2, \ldots, a_n$, where $n$ is even. Some of the blocks can be equal in size. She would like to put all these blocks one onto another to form a fancy stack.

Let $b_1, b_2, \ldots, b_n$ be the sizes of blocks in the stack from top to bottom. Since Fiona is using all her blocks, $b_1, b_2, \ldots, b_n$ must be a permutation of $a_1, a_2, \ldots, a_n$. Fiona thinks the stack is fancy if both of the following conditions are satisfied:

• The second block is strictly bigger than the first one, and then each block is alternately strictly smaller or strictly bigger than the previous one. Formally, $b_1 \lt b_2 \gt b_3 \lt b_4 \gt \ldots \gt b_{n-1} \lt b_n$.
• The sizes of the blocks on even positions are strictly increasing. Formally, $b_2 \lt b_4 \lt b_6 \lt \ldots \lt b_n$ (remember that $n$ is even).

Two stacks are considered different if their corresponding sequences $b_1, b_2, \ldots, b_n$ differ in at least one position.

Fiona wants to know how many different fancy stacks she can build with all of her blocks. Since large numbers scare Fiona, find this number modulo $998\,244\,353$.

小菲奥娜有一组 $n$ 个大小各异的积木，大小分别为 $a_1, a_2, \ldots, a_n$，其中 $n$ 为偶数。部分积木的大小可能相等。她希望将所有这些积木自上而下叠放成一个“花式”堆叠。

设堆叠中自上而下的积木大小依次为 $b_1, b_2, \ldots, b_n$。由于菲奥娜使用了全部积木，因此 $b_1, b_2, \ldots, b_n$ 必须是 $a_1, a_2, \ldots, a_n$ 的一个排列。菲奥娜认为该堆叠是“花式”的，当且仅当同时满足以下两个条件：

• 第二块积木严格大于第一块，之后每一块积木与前一块严格交替地更小或更大。形式化地，满足：
  $b_1 \lt b_2 \gt b_3 \lt b_4 \gt \ldots \gt b_{n-1} \lt b_n$。
• 所有位于偶数位置（即第 $2,4,6,\ldots,n$ 位）的积木大小严格递增。形式化地，满足：
  $b_2 \lt b_4 \lt b_6 \lt \ldots \lt b_n$（注意 $n$ 是偶数）。

若两个堆叠对应的序列 $b_1, b_2, \ldots, b_n$ 至少在一个位置上不同，则认为它们是不同的堆叠。

菲奥娜想知道：用她所有的积木，一共能搭建出多少种不同的“花式”堆叠？由于大数会吓到菲奥娜，请将该数目对 $998\,244\,353$ 取模后输出。

Each input contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 2500$). Description of the test cases follows.

The first line of each test case contains a single integer $n$ — the number of blocks at Fiona's disposal ($2 \le n \le 5000$; $n$ is even). The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ — the sizes of the blocks in non-decreasing order ($1 \le a_1 \le a_2 \le \dotsb \le a_n \le n$).

It is guaranteed that the sum of $n$ over all test cases does not exceed $5000$.

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

每个测试用例的第一行包含一个整数 $n$ —— Fiona 所拥有的方块数量（$2 \le n \le 5000$；且 $n$ 为偶数）。第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$ —— 方块的尺寸，按非递减顺序排列（$1 \le a_1 \le a_2 \le \dotsb \le a_n \le n$）。

保证所有测试用例中 $n$ 的总和不超过 $5000$。

For each test case, print the number of ways to build a fancy stack, modulo $998\,244\,353$.

对于每个测试用例，输出构建一个“花式”堆栈的方案数，对 $998\,244\,353$ 取模。