← 返回题目列表

Codeforces · 1666/F

F. 花式堆栈

中文机器翻译题面 查看原题

小菲奥娜有一系列不同大小的 $$$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$$$。
  • 偶数位置上的块的大小严格增加。形式上, $$$b_2 \lt b_4 \lt b_6 \lt \ldots \lt b_n$$$ (记住 $$$n$$$ 是偶数)。

如果两个堆栈的对应序列 $$$b_1, b_2, \ldots, b_n$$$ 至少在一个位置不同,则认为两个堆栈不同。

菲奥娜想知道她可以用她的所有积木搭建多少个不同的花式堆叠。由于大数会吓到菲奥娜,请用 $$$998\,244\,353$$$ 求该数。

输入

每个输入包含多个测试用例。第一行包含测试用例的数量 $$$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$$$。

输出

对于每个测试用例,打印构建奇特堆栈的方法数量,以 $$$998\,244\,353$$$ 为模。

示例

输入
复制

2
4
1 2 3 4
8
1 1 2 3 4 4 6 7

输出
复制

2
4