You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

有一张 $n$ 个点的无向图，初始第 $i$ 个点的点权为 $a_i$，而图上没有连边。

出于某些原因，你需要在图上建造 尽可能多 的边，满足：图无重边、自环；且不存在 互不相同的 整数 $u, v, w$ 满足 $a_u \leq a_v \leq a_w$，同时 $u, v$ 节点之间有连边、$v, w$ 节点之间有连边。

在满足建造边数最大的情况下，求共有多少种不同的建造方案。因为答案可能很大，所以请对 $998244353$ 取模。

输入格式

从 cities.in 中读入数据。

本题单个测试点内有多组数据。

第一行，一个整数 $t$，描述数据组数。对于每组数据：

• 第一行，一个整数 $n$。
• 接下来一行 $n$ 个整数 $a_1, \ldots, a_n$。

输出格式

输出到 cities.out 中。

对于每组数据，输出一行一个整数，表示答案对 $998244353$ 取模后的结果。

样例

3
2
7 7
3
1 2 3
5
1 3 2 2 5

1
2
1

样例 1 解释

对于第一组数据，唯一符合题意的边集是 $\{(1, 2)\}$。

对于第二组数据，一个符合题意的边集是 $\{(1, 2), (1, 3)\}$，或是 $\{(1, 3), (2, 3)\}$。共有 $2$ 种。

对于第三组数据，唯一符合题意的边集是 $\{(1, 2), (1, 5), (2, 3), (2, 4), (3, 5), (4, 5)\}$。

附加样例

见 下发 的 cities/cities2.in 和 cities/cities2.ans 至 cities/cities3.in 和 cities/cities3.ans。

数据规模与约定

本题采用捆绑测试。

• Subtask 1（20 pts）：$t \leq 15$，$n \leq 5$，$a_i \leq 10$。
• Subtask 2（30 pts）：保证 $a_1, \ldots, a_n$ 互不相同。
• Subtask 3（50 pts）：无特殊限制。

对于所有数据，保证 $1 \leq t \leq 10^3$，$\sum n \leq 3\times 10^5$，$n \geq 1$，$1 \leq a_i \leq 10^9$。