/ 
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 700 点
問題文
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 で割った余りを求めてください．
制約
- 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\} の 3 通りです．
入力例 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
Score : 700 points
Problem Statement
We have N balls arranged in a row, numbered 1 to N from left to right. Ball i has an integer A_i written on it.
You can do the following operation any number of times.
- Choose three consecutive balls x, y, z (1 \leq x < y < z \leq N). Here, A_x \neq A_y and A_y \neq A_z must hold. Then, eat Ball y. After this operation, Balls x and z are considered adjacent.
Find the number of possible sets of balls remaining in the end, modulo 998244353.
Constraints
- 2 \leq N \leq 200000
- 1 \leq A_i \leq N
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N A_1 A_2 \cdots A_N
Output
Print the answer.
Sample Input 1
4 1 2 1 2
Sample Output 1
3
There are three possible sets of balls remaining in the end: \{1,2,3,4\},\{1,2,4\},\{1,3,4\}.
Sample Input 2
5 5 4 3 2 1
Sample Output 2
8
Different sequences of operations are not distinguished if they result in the same set of balls.
Sample Input 3
5 1 2 3 2 1
Sample Output 3
8
Different sets of remaining balls are distinguished even if they have the same sequence of integers written on them.
Sample Input 4
9 1 4 2 2 9 6 9 6 6
Sample Output 4
14