← 返回题目列表

Codeforces · 2069/C

C. 美丽的序列

中文机器翻译题面 查看原题

让我们调用一个整数序列 美丽 如果满足以下条件:

  • 其长度至少为$$$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$$$ 为模。

示例

输入
复制

4
7
3 2 1 2 2 1 3
4
3 1 2 2
3
1 2 3
9
1 2 3 2 1 3 2 2 3

输出
复制

3
0
1
22

注意

在示例的第一个测试用例中,以下子序列很漂亮:

  • $$$[a_3,a_4,a_7]$$$;
  • $$$[a_3,a_5,a_7]$$$;
  • $$$[a_3、a_4、a_5、a_7]$$$。