AT_arc206_c [ARC206C] Tree Sequence

$ 1 $ 以上 $ N $ 以下の整数からなる長さ $ N $ の数列 $ B=(B_1,\ldots,B_N) $ が良い数列であるとは，以下の条件を満たすことをいいます． - 任意の区間 $ [l,r]\ (1\leq l \leq r \leq N) $ に対して，以下の条件が成り立つような整数 $ x\ (l\leq x\leq r) $ が存在する： - 頂点に $ 1 $ から $ N $ の番号が付いた $ N $ 頂点 $ 0 $ 辺のグラフを用意する．全ての $ l \leq i \leq r $ について， $ i\neq x $ ならば頂点 $ i $ と頂点 $ B_i $ の間に辺を張る．このとき 頂点 $ l, l+1,\ldots,r $ が木をなしている．つまり，頂点 $ l, l+1,\ldots,r $ が連結になっている． 各要素が $ 1 $ 以上 $ N $ 以下の整数，または $ -1 $ であるような数列 $ A=(A_1,\ldots,A_N) $ が与えられます． $ A $ のうち $ -1 $ であるような要素を $ 1 $ 以上 $ N $ 以下の整数に置き換える方法であって， $ A $ が良い数列になるようなものの個数を $ 998244353 $ で割ったあまりを求めてください．

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

$ A $ のうち $ -1 $ であるような要素を $ 1 $ 以上 $ N $ 以下の整数に置き換える方法であって， $ A $ が良い数列になるようなものの個数を $ 998244353 $ で割ったあまりを出力せよ．

### Sample Explanation 1 条件を満たす置き換え方は以下の $ 7 $ 個です． - $ (1,1,2) $ - $ (2,1,2) $ - $ (2,2,2) $ - $ (2,3,1) $ - $ (2,3,2) $ - $ (2,3,3) $ - $ (3,1,2) $ 例えば $ A=(1,1,2) $ の場合に区間 $ [1,2] $ が条件を満たすことは， $ x=1 $ とすると頂点 $ 2 $ と頂点 $ A_2=1 $ が結ばれ頂点 $ 1,2 $ が木をなすことから確認できます． 同様に区間 $ [1,1],[2,2],[3,3],[2,3],[1,3] $ も条件を満たすため， $ (1,1,2) $ は良い数列です． ### Sample Explanation 2 条件を満たす置き換え方は以下の $ 3 $ 個です． - $ (2,3,1) $ - $ (2,3,2) $ - $ (2,3,3) $ ### Constraints - 入力される数値は全て整数 - $ 1\leq N\leq 2\times 10^5 $ - $ 1\leq A_i\leq N $ または $ A_i=-1 $