CFCF2144E1.Looking at Towers (easy version)

普及+/提高

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

这是该问题的简单版本。简单版与困难版的唯一区别在于 $t$ 和 $n$ 的约束条件。

现有一排 $m$ 个塔，第 $i$ 个塔的高度为 $h_i$ 。

如果你从左侧观察这排塔，你能看到所有严格高于前面所有塔的塔。同理，如果你从右侧观察这排塔，你能看到所有严格高于其右侧所有塔的塔。例如，如果这些塔的高度为 $[3, 5, 5, 7, 4, 6, 7, 2, 4]$ ，那么：

设 $L(h)$ 为从左侧能看到的塔的高度集合， $R(h)$ 为从右侧能看到的塔的高度集合，当这排塔的高度序列为 $h$ 时。对于上述例子， $L(h) = \{3, 5, 7\}$ ， $R(h) = \{4, 7\}$ 。

现给定一个序列 $a_1, a_2, \dots, a_n$ 。你的任务是计算出其所有子序列 $a'$ 的数量，满足 $L(a) = L(a')$ 且 $R(a) = R(a')$ 。其中两个子序列不同当且仅当所选元素的下标不同。

第一行包含一个整数 $t$ （ $1 \leq t \leq 100$ ），表示测试用例的数量。

每组测试用例包含两行：

额外输入约束：所有测试用例中 $n$ 之和不超过 $5000$ 。

对于每个测试用例，输出一个整数，表示给定序列 $a$ 的满足 $L(a) = L(a')$ 且 $R(a) = R(a')$ 的子序列 $a'$ 的数量。由于答案可能很大，请输出对 $998244353$ 取模后的结果。

输入#1

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

输出#1

在第一个样例中， $L(a) = \{4, 8\}$ ， $R(a) = \{3, 8\}$ 。包含在答案中的子序列有：

在第二个样例中，唯一合法的子序列就是原序列本身。