题目描述

我们有 $N$ 个球按顺序排列，从左到右编号为 $1$ 到 $N$。第 $i$ 个球上写着整数 $A_i$。

你可以进行以下操作任意次数：

• 选择三个连续的球 $x, y, z$ $(1 \\leq x < y < z \\leq N$)。此时，需要满足 $A_x \\neq A_y$ 和 $A_y \\neq A_z$。然后，吃掉球 $y$。这个操作之后，球 $x$ 和 $z$ 被认为是相邻的。

求最后剩下的可能的球的集合数，对 $998244353$ 取余。

约束条件

• $2 \\leq N \\leq 200000$
• $1 \\leq A_i \\leq N$
• 输入中的所有值都是整数。

输入

从标准输入中以以下格式给出输入：

$N$ $A_1$ $A_2$ $\\cdots$ $A_N$

输出

输出答案。

示例输入 1

4
1 2 1 2

示例输出 1

3

最后剩下的可能的球的集合数有三种：$\\{1,2,3,4\\},\\{1,2,4\\},\\{1,3,4\\}$。

示例输入 2

5
5 4 3 2 1

示例输出 2

8

相同的球的集合不会被区分。

示例输入 3

5
1 2 3 2 1

示例输出 3

8

即使他们有相同的整数序列，不同的剩余球的集合也不会被区分。

示例输入 4

9
1 4 2 2 9 6 9 6 6

示例输出 4

14