← 返回题目列表

Codeforces · 1912/K

K. 金的任务

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

在 Kombinatoria 古老学院的长期被遗忘的大厅里,一位名叫 Kim 的天才数学家面临着一个不寻常的挑战。他们发现了一个旧的整数序列,这被认为是来自传奇的 Kombinatoria 甲骨文的神秘消息,金想要破译其隐藏的含义。

Kim 的任务是找到序列中的特定模式,称为 和谐的子序列。这些是非凡的子序列,其中每三个连续数字的总和为偶数,并且每个子序列的长度必须至少为三个数字。

给定一个长度为 $$$n$$$ 的序列 $$$a_i$$$ ($$$1 \le i \le n$$$),其 子序列 长度为 $$$m$$$ 的 等于 $$$a_{b_1}, a_{b_2}, \ldots, a_{b_m}$$$ 并且由一组 $$$m$$$ 索引 $$$b_j$$$ 唯一定义,使得 $$$1 \le b_1 \lt b_2 \lt \ldots \lt b_m \le n$$$。由不同索引集 $$$b_j$$$ 给出的子序列被认为是不同的。

Kim 的探索有一个转折:这些和谐子序列的数量可能会令人难以承受。为了有效地报告结果,Kim 必须计算这些子序列的总数,将答案表示为除以数字 $$$998\,244\,353$$$ 后的余数。

输入

第一行包含一个整数 $$$n$$$ — 序列的长度 ($$$3 \le n \le 2 \cdot 10^5$$$)。

第二行包含 $$$n$$$ 以空格分隔的整数 $$$a_i$$$ — 序列的元素 ($$$1 \le a_i \le 2 \cdot 10^5$$$)。

输出

输出一个数字——和谐子序列的数量,以 $$$998\,244\,353$$$ 为模。

示例

输入
复制

3
1 2 3

输出
复制

1

输入
复制

5
2 8 2 6 4

输出
复制

16

输入
复制

5
5 7 1 3 5

输出
复制

0

输入
复制

11
3 1 4 1 5 9 2 6 5 3 6

输出
复制

386

输入
复制

54
2 1 1 1 1 2 1 2 2 2 2 1 1 1 2 1 1 2
2 1 2 2 2 2 2 2 2 1 1 1 2 2 1 1 1 1
2 2 1 1 2 2 2 2 2 1 1 1 2 2 1 2 1 1

输出
复制

0

注意

在为第五个样本提供的输入数据中,为了清楚起见,数字序列被分成三行,但应该理解的是,在实际测试数据中,序列是在一行中给出的。本例中和谐子序列的实际数量为 $$$4\,991\,221\,765 = 5 \times 998\,244\,353$$$,因此除以数字 $$$998\,244\,353$$$ 后求余数,结果输出为零。