← 返回题目列表

Codeforces · 1876/D

D. 词法色谱

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

Pak Chanek 热爱他的教师,即印度尼西亚大学 (Fasilkom) 计算机科学学院。他想尝试一下学院标志的颜色,蓝色和红色。

有一个数组$$$a$$$,由$$$n$$$个元素组成,元素$$$i$$$的值为$$$a_i$$$。 Pak Chanek 希望将数组中的每个元素着色为蓝色或红色,以满足以下条件:

- 如果所有蓝色元素都形成子序列$$$^\dagger$$$,所有红色元素也是如此,则蓝色子序列按字典顺序严格小于红色子序列$$$^\ddagger$$$。
- 数组 $$$a$$$ 没有任何不平衡的子数组。子数组不平衡当且仅当存在值 $$$k$$$,使得该子数组中值为 $$$k$$$ 的蓝色元素数量与值为 $$$k$$$ 的红色元素数量之间的绝对差为 $$$2$$$ 或更多。
- 请注意,可以将数组的每个元素着色为相同的颜色。

有多少种不同的颜色满足所有这些条件?由于答案可能非常大,请打印对 $$$998\,244\,353$$$ 取模的答案。当且仅当至少有一个元素在一种颜色中为蓝色,而在另一种颜色中为红色时,两种颜色才是不同的。

$$$^\dagger$$$ 数组的子序列是可以通过删除一些元素(可能没有)从数组中获得的序列,而不改变剩余元素的顺序。

$$$^\ddagger$$$ 令 $$$p$$$ 和 $$$q$$$ 为两个不同的序列。当且仅当 $$$p$$$ 是 $$$q$$$ 的前缀,或者存在索引 $$$i$$$ 使得 $$$p_j=q_j$$$ 对于每个 $$$1\leq j<i$$$ 和 $$$p_i<q_i$$$ 成立时,序列 $$$p$$$ 被认为按字典顺序小于序列 $$$q$$$。特别是,空序列在字典顺序上总是小于任何非空序列。

输入

第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 2\cdot10^5$$$) — 数组 $$$a$$$ 的大小。

第二行包含 $$$n$$$ 整数 $$$a_1,a_2,a_3,\ldots,a_n$$$ ($$$1\leq a_i\leq2\cdot10^5$$$)。

输出

一个整数,表示满足所有问题条件的不同着色的数量,以 $$$998\,244\,353$$$ 为模。

示例

输入 #1

8
1 3 1 2 3 2 3 3

输出 #1

3

输入 #2

1
265

输出 #2

1

注意

在第一个示例中,为从索引 $$$1$$$ 到索引 $$$8$$$ 的所有元素着色的 $$$3$$$ 方法是:

- 蓝色,红色,红色,蓝色,蓝色,红色,红色,蓝色。
- 蓝色,红色,红色,红色,蓝色,蓝色,红色,蓝色。
- 红,红,蓝,蓝,蓝,红,红,蓝。

举个例子,如果我们将索引 $$$1$$$ 到索引 $$$8$$$ 的元素着色为红色、红色、蓝色、红色、红色、蓝色、蓝色、蓝色,则它不是有效的着色,因为对于子数组 $$$a[2..6]$$$,有 $$$0$$$ 蓝色元素的值为 $$$3$$$ 和 $$$2$$$ 红色元素的值为 $$$2$$$ $$$3$$$,使子数组 $$$a[2..6]$$$ 成为不平衡子数组。