CF2069C.Beautiful Sequence

我们称一个整数序列为美丽的（beautiful），当且仅当满足以下条件：

• 序列长度至少为 $3$；
• 对于除第一个元素外的每个元素，其左侧存在一个比它小的元素；
• 对于除最后一个元素外的每个元素，其右侧存在一个比它大的元素；

例如，$[1, 4, 2, 4, 7]$ 和 $[1, 2, 4, 8]$ 是美丽的，但 $[1, 2]$、$[2, 2, 4]$ 和 $[1, 3, 5, 3]$ 不是。

注意：子序列是指通过删除原序列中某些元素（不改变剩余元素的顺序）得到的新序列。

给定一个大小为 $n$ 的整数数组 $a$，其中每个元素均为 $1$ 到 $3$ 之间的整数。你的任务是计算数组 $a$ 中美丽子序列的数量。由于答案可能很大，请将其对 $998244353$ 取模后输出。

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

每个测试用例的第一行包含一个整数 $n$（$3 \le n \le 2 \cdot 10^5$）。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 3$）。

输入额外约束：所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。

对于每个测试用例，输出一个整数——数组 $a$ 中美丽子序列的数量对 $998244353$ 取模后的结果。

在示例的第一个测试用例中，以下子序列是美丽的：

• $[a_3, a_4, a_7]$；
• $[a_3, a_5, a_7]$；
• $[a_3, a_4, a_5, a_7]$。

翻译由 DeepSeek R1 完成