题目描述

有 $N$ 个球排成一列，从左到右依次编号为 $1$ 到 $N$。第 $i$ 个球上写有整数 $A_i$。

你可以任意次重复以下操作：

• 选择连续排列的 $3$ 个球 $x, y, z$（$1 \leq x < y < z \leq N$），要求 $A_x \neq A_y$ 且 $A_y \neq A_z$。然后吃掉球 $y$。此操作后，球 $x$ 和球 $z$ 被认为在序列中连续排列。

请你求出，最终可能剩下的球的集合有多少种，答案对 $998244353$ 取模。

输入格式

输入通过标准输入给出，格式如下：

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

输出格式

请输出答案。

样例 1

输入

4
1 2 1 2

输出

3

样例 2

输入

5
5 4 3 2 1

输出

8

样例 3

输入

5
1 2 3 2 1

输出

8

样例 4

输入

9
1 4 2 2 9 6 9 6 6

输出

14

说明/提示

限制条件

• $2 \leq N \leq 200000$
• $1 \leq A_i \leq N$
• 输入的所有值均为整数。

样例解释 1

最终可能剩下的球的集合有 $\{1,2,3,4\},\{1,2,4\},\{1,3,4\}$ 共 $3$ 种。

样例解释 2

即使操作方法不同，只要最终剩下的球的集合相同，也不区分。

样例解释 3

即使剩下的球上写的整数排列相同，只要球的集合不同，也要区分。

由 ChatGPT 4.1 翻译