AT_arc206_c [ARC206C] Tree Sequence

A sequence $ B=(B_1,\ldots,B_N) $ of length $ N $ consisting of integers between $ 1 $ and $ N $ (inclusive) is called a good sequence if and only if it satisfies the following condition: - For every interval $ [l,r]\ (1\leq l \leq r \leq N) $ , there exists an integer $ x\ (l\leq x\leq r) $ such that the following condition holds: - Prepare a graph with $ N $ vertices numbered from $ 1 $ to $ N $ and zero edges. For each $ l \leq i \leq r $ , if $ i\neq x $ , add an edge between vertices $ i $ and $ B_i $ . Then, vertices $ l, l+1,\ldots,r $ form a tree. That is, vertices $ l, l+1,\ldots,r $ are connected. You are given a sequence $ A=(A_1,\ldots,A_N) $ where each element is either an integer between $ 1 $ and $ N $ , or $ -1 $ . Find the number, modulo $ 998244353 $ , of ways to replace the elements that are $ -1 $ in $ A $ with integers between $ 1 $ and $ N $ such that $ A $ becomes a good sequence.

The input is given from Standard Input in the following format: > $ N $ $ A_1 $ $ \cdots $ $ A_N $

Output the number, modulo $ 998244353 $ , of ways to replace the elements that are $ -1 $ in $ A $ with integers between $ 1 $ and $ N $ (inclusive) such that $ A $ becomes a good sequence.

### Sample Explanation 1 The replacements that satisfy the condition are the following seven: - $ (1,1,2) $ - $ (2,1,2) $ - $ (2,2,2) $ - $ (2,3,1) $ - $ (2,3,2) $ - $ (2,3,3) $ - $ (3,1,2) $ For example, in the case of $ A=(1,1,2) $ , that the interval $ [1,2] $ satisfies the condition can be confirmed by setting $ x=1 $ , where vertices $ 2 $ and $ A_2=1 $ are connected and vertices $ 1,2 $ form a tree. Similarly, intervals $ [1,1],[2,2],[3,3],[2,3],[1,3] $ also satisfy the condition, so $ (1,1,2) $ is a good sequence. ### Sample Explanation 2 The replacements that satisfy the condition are the following three: - $ (2,3,1) $ - $ (2,3,2) $ - $ (2,3,3) $ ### Constraints - All input values are integers. - $ 1\leq N\leq 2\times 10^5 $ - $ 1\leq A_i\leq N $ or $ A_i=-1 $