CF1666F Fancy Stack

有 $n$ 块木块（$n$ 为偶数），长度依次为 $a_1,a_2,…,a_n$（可能会相同），现在想要把它们叠成一叠，且满足以下条件（令这一叠木块从上到下的长度依次为 $b_1,b_2,…,b_n$ 且 $b$ 数组为 $a$ 数组的一个排列）： - 从上往下的第二块木块长度严格大于第一块，之后的每一块木块交替严格小于或严格大于上一个块，也就是说，满足 $b_1b_3…>b_{n-1}

每个测试点有多组数据。第一行读入一个正整数 $t$ 表示数据组数（$1\le t\le 2500$）。接下来依次读入 $t$ 组数据： 每组数据的第一行一个正整数 $n$ 表示木块数（$2\le n\le 5000$ 且为偶数）。 第二行 $n$ 个正整数 $a_1,a_2,…,a_n$ 依次表示每块木块的长度且 $1\le a_1\le a_2\le …\le a_n\le n$。 所有数据的 $n$ 之和不超过 $5000$。

对于每组数据，输出方案数，对 $998244353$ 取模。