AT_arc187_e [ARC187E] Replace Triplets

[problemUrl]: https://atcoder.jp/contests/arc187/tasks/arc187_e 長さ $ N $ の数列 $ A=(A_1,\ldots,A_N) $ が与えられます．ここで $ N $ は $ 3 $ 以上の整数です． あなたは以下の操作を $ 0 $ 回以上任意の回数行うことができます． - $ 1\leq\ i\leq\ N $ かつ $ A_i=A_{i+1}=A_{i+2} $ を満たす整数 $ i $ を選ぶ．$ A_i,A_{i+1},A_{i+2} $ のうちいずれか $ 2 $ つをそれぞれ $ 1 $ 以上 $ N $ 以下の整数で置き換える．ここで，$ A_{N+1}=A_1,A_{N+2}=A_2 $ とする． 最終的に得られる $ A $ のうち，$ A $ が $ (1,\ldots,N) $ の順列であるものの個数を $ 998244353 $ で割ったあまりを求めてください．

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

答えを出力せよ．

### 制約 - 入力される数値は全て整数 - $ 3\leq\ N\leq\ 5\times\ 10^5 $ - $ 1\leq\ A_i\leq\ N $ ### Sample Explanation 1 例えば，最終的に $ A=(1,2,4,3,5,6) $ という順列を以下の手順で得ることができます． - $ i=5 $ として操作を行う．$ A_5 $ を $ 3 $ で，$ A_6 $ を $ 6 $ で置き換える．$ A=(1,2,3,3,3,6) $ となる． - $ i=3 $ として操作を行う．$ A_3 $ を $ 4 $ で，$ A_5 $ を $ 5 $ で置き換える．$ A=(1,2,4,3,5,6) $ となる． 最終的に得られる $ A $ であって $ (1,\ldots,6) $ の順列であるものの個数は $ 360 $ 個です． ### Sample Explanation 2 最終的に得られる $ A $ であって $ (1,\ldots,5) $ の順列であるものは存在しません．