CF2144E1.Looking at Towers (easy version)

This is the easy version of the problem. The only differences between the easy and the difficult version are the constraints on $t$ and $n$.

Consider a row of $m$ towers; the height of the $i$-th tower in the row is $h_i$.

If you look at this row of towers from the left, you see all towers that are strictly higher than all towers before them. Similarly, if you look at this row of towers from the right, you see all towers that are strictly higher than all towers after them. For example, if the towers have heights $[3, 5, 5, 7, 4, 6, 7, 2, 4]$, then:

• when looking from the left, you see towers with heights $3$, $5$ and $7$;
• when looking from the right, you see towers with heights $7$ and $4$.

Let $L(h)$ be the set of heights you see from the left, and $R(h)$ be the set of heights you see from the right when the sequence of heights is $h$. In the example above, $L(h) = {3, 5, 7}$, and $R(h) = {4, 7}$.

You are given a sequence $a_1, a_2, \dots, a_n$. Your task is to calculate the number of subsequences of $a$ such that $L(a) = L(a')$ and $R(a) = R(a')$, where $a'$ is the subsequence you consider. Two subsequences are different if indices of chosen elements are different.

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

考虑一排共 $m$ 座塔；其中第 $i$ 座塔的高度为 $h_i$。

若从左侧观察这排塔，则能看到所有严格高于其左侧所有塔的塔；类似地，若从右侧观察，则能看到所有严格高于其右侧所有塔的塔。例如，若塔的高度序列为 $[3, 5, 5, 7, 4, 6, 7, 2, 4]$，则：

• 从左侧观察时，能看到高度为 $3$、$5$ 和 $7$ 的塔；
• 从右侧观察时，能看到高度为 $7$ 和 $4$ 的塔。

令 $L(h)$ 表示当塔高序列为 $h$ 时，从左侧观察所见到的塔的高度集合；$R(h)$ 表示从右侧观察所见到的塔的高度集合。在上述例子中，$L(h) = \{3, 5, 7\}$，而 $R(h) = \{4, 7\}$。

给定一个序列 $a_1, a_2, \dots, a_n$。你的任务是计算 $a$ 的子序列个数，使得对于所考虑的子序列 $a'$，满足 $L(a) = L(a')$ 且 $R(a) = R(a')$。若两个子序列所选元素的下标不同，则认为它们是不同的子序列。

The first line contains one integer $t$ ($1 \le t \le 100$) — the number of test cases.

Each test case consists of two lines:

• the first line contains one integer $n$ ($1 \le n \le 5000$);
• the second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$).

Additional constraint on the input: the sum of $n$ over all test cases does not exceed $5000$.

第一行包含一个整数 $t$（$1 \le t \le 100$）—— 测试用例的数量。

每个测试用例由两行组成：

• 第一行包含一个整数 $n$（$1 \le n \le 5000$）；
• 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^9$）。

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

For each test case, print one integer — the number of subsequences $a'$ of the given sequence $a$ such that $L(a) = L(a')$ and $R(a) = R(a')$. Since it might be huge, print it modulo $998244353$.

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

In the first example, $L(a) = {4, 8}$, $R(a) = {3, 8}$. The subsequences included in the answer are:

• $[4, 8, 3]$ (the $1$-st, the $4$-th and the $5$-th element);
• $[4, 8, 3]$ (the $3$-rd, the $4$-th and the $5$-th element);
• $[4, 2, 8, 3]$ (the $1$-st, the $2$-nd, the $4$-th and the $5$-th element);
• $[4, 4, 8, 3]$ (the $1$-st, the $3$-rd, the $4$-th and the $5$-th element);
• $[4, 2, 4, 8, 3]$ (the whole sequence).

In the second example, the only valid subsequence is the given sequence itself.

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

• $[4, 8, 3]$（第 $1$ 个、第 $4$ 个和第 $5$ 个元素）；
• $[4, 8, 3]$（第 $3$ 个、第 $4$ 个和第 $5$ 个元素）；
• $[4, 2, 8, 3]$（第 $1$ 个、第 $2$ 个、第 $4$ 个和第 $5$ 个元素）；
• $[4, 4, 8, 3]$（第 $1$ 个、第 $3$ 个、第 $4$ 个和第 $5$ 个元素）；
• $[4, 2, 4, 8, 3]$（整个序列）。

在第二个例子中，唯一有效的子序列就是给定的序列本身。