AT_abc446_g [ABC446G] 221 Subsequence

正整数からなる数列 $ X = (X_1, \dots, X_n) $ に対し、その連長圧縮の任意の (長さ・値) ペアにおいて長さと値が等しいとき、かつそのときに限り、 $ X $ を **221 数列** と呼びます。より厳密には、以下の条件を満たす数列を 221 数列であるとします。 - $ 1 \leq l \leq r \leq n $ を満たす整数組 $ (l, r) $ が以下の $ 3 $ つの条件をすべて満たすならば、必ず $ (r-l+1) = X_l $ が成り立つ。 - $ l = 1 $ または ( $ l \geq 2 $ かつ $ X_{l-1} \neq X_l $ ) - $ r = n $ または ( $ r \leq n-1 $ かつ $ X_{r+1} \neq X_r $ ) - $ X_l = X_{l+1} = \dots = X_r $ たとえば、 $ (2,2,3,3,3,1,2,2) $ は 221 数列ですが、 $ (1,1) $ や $ (4,4,1,4,4) $ は 221 数列ではありません。 長さ $ N $ の正整数列 $ A = (A_1, \dots, A_N) $ が与えられます。 $ A $ の空でない(連続とは限らない)部分列であって、221 数列であるものの個数を $ 998244353 $ で割ったあまりを求めてください。 ただし、異なる位置から取り出した部分列であっても、数列として一致するものは区別せずまとめて $ 1 $ 通りとして数えます。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ A_1 $ $ A_2 $ $ \cdots $ $ A_N $

答えを $ 1 $ 行に出力せよ。

### Sample Explanation 1 $ A $ の空でない部分列として現れる 221 数列は以下の $ 5 $ 通りです。 - $ (1) $ - $ (1,2,2) $ - $ (2,2) $ - $ (2,2,1) $ - $ (2,2,1,2,2) $ ### Sample Explanation 2 $ A $ の空でない部分列として現れる 221 数列は存在しません。 ### Constraints - $ 1 \leq N \leq 500\,000 $ - $ 1 \leq A_i \leq N $ - 入力される値はすべて整数