题目描述

$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$

输出格式

答えを出力せよ．

题目大意

给定 $N$ 个元素的序列，每次操作可以选择连续三个整数 $A_{i-1}\ne A_i$ 且 $A_i\ne A_{i + 1}$ ，然后将 $A_i$ 删除。求最终可能得到的序列数量。

4
1 2 1 2

3

5
5 4 3 2 1

8

5
1 2 3 2 1

8

9
1 4 2 2 9 6 9 6 6

14

提示

制約

• $2\ \leq\ N\ \leq\ 200000$
• $1\ \leq\ A_i\ \leq\ N$
• 入力される値はすべて整数である

Sample Explanation 1

最終的に残っているボールの集合として考えられるのは，$\{1,2,3,4\},\{1,2,4\},\{1,3,4\}$ の $3$ 通りです．

Sample Explanation 2

異なる操作方法でも，最終的に残るボールの集合が同じであれば区別しません．

Sample Explanation 3

残るボールに書かれた整数を並べた列が同じでも，ボールの集合が異なる場合は区別されます．