题目描述

对于一个数组 $a_{1\sim m}$，可以定义其前缀最大值数组 $f(a)=b$，其中 $b_k=\max_{i=1}^k \{a_i\}$，即 $b_k$ 是 $a_1,a_2,\dots,a_k$ 中的最大值。容易验证 $b$ 的长度也是 $m$。

对于一个长度为 $2n$ 的排列 $p$，Carol 想要研究其 $f(p)$ 的多样性，但完全未知的排列太乏味，所以 Carol 准备了一个部分完整的 $p$：只有 $p_{1\sim n}$ 是确定的！

由于 $p$ 的长度是 $2n$，所以 Carol 实际想解决的问题是，对于所有长度为 $2n$ 的排列 $q$，对所有 $1\leq i\leq n$ 都满足 $q_i=p_i$，其 $f(q)$ 有多少种不同的取值？

例如，当 $n=2,p=[2,3]$ 时，可能的排列 $q$ 就有 $[2,3,1,4],[2,3,4,1]$ 两种，对应的 $f(q)$ 分别为 $[2,3,3,4]$ 和 $[2,3,4,4]$，共两种不同的取值；但当 $n=2,p=[4,1]$ 时，符合条件的 $q$ 的 $f(q)$ 只能取 $[4,4,4,4]$，只有一种不同的取值。

由于答案可能很大，你只需要输出其对 $998244353$ 取模后的结果。

输入格式

第一行一个整数 $T$ 表示数据组数，对于每组数据：

第一行一个整数 $n$。

第二行 $n$ 个整数 $p_{1\sim n}$。

输出格式

对于每组数据，输出一行一个整数表示答案。

5
1
1
2
2 3
3
4 1 2
3
6 3 4
7
4 2 7 1 9 8 3

1
2
5
1
297

样例解释 1

对于第三组数据，当q取[4,1,2,6,3,5]和[4,1,2,6,5,3]时，f(q)都是[4,4,4,6,6,6]，其余f(q)都互不相同，所以答案为6-1=5。

数据范围

对于 $30\%$ 的数据，$\sum n\leq 10$。

对于 $60\%$ 的数据，$\sum n\leq 3000$。

对于 $100\%$ 的数据，$1\leq T\leq 10^5$，$1\leq n\leq \sum n\leq 10^6$，$1\leq p_i\leq 2n$，$\forall 1\leq i<j\leq n,p_i\neq p_j$。