AT_arc216_b [ARC216B] Range Mex Sum

正整数 $ N $ および整数列 $ A=(A_1,A_2,\ldots,A_N) $ が与えられます． $ A_i $ は $ -1 $ 以上 $ N-1 $ 以下であり， $ 1\leq i\lt j\leq N $ に対し， $ A_i\neq -1 $ かつ $ A_j\neq -1 $ ならば $ A_i\neq A_j $ です． 次のクエリを $ Q $ 回解いてください． - 整数 $ l,r\ (1\leq l\leq r\leq N) $ が与えられる． $ (0,1,\ldots,N-1) $ の順列 $ P=(P_1,P_2,\ldots,P_N) $ であって， $ A_i\neq -1\implies P_i=A_i $ を満たすようなもの全てに対する $ \mathrm{mex}(\lbrace P_l,P_{l+1}, \ldots,P_r\rbrace) $ の総和を $ 998244353 $ で割った余りを求めよ． $ \mathrm{mex}(S) $ とは 非負整数からなる集合 $ S $ に対して， $ S $ に含まれない最小の非負整数を $ \mathrm{mex}(S) $ と定義します．

入力は以下の形式で標準入力から与えられる． > $ N $ $ Q $ $ A_1 $ $ A_2 $ $ \ldots $ $ A_N $ $ \mathrm{query}_1 $ $ \mathrm{query}_2 $ $ \vdots $ $ \mathrm{query}_Q $ 各クエリは以下の形式で与えられる． > $ l $ $ r $

$ Q $ 行出力せよ． $ i $ 行目には $ \mathrm{query}_i $ に対する答えを出力せよ．

### Sample Explanation 1 $ A_i\neq -1\implies P_i=A_i $ であるような順列 $ P $ は $ (0, 1, 2) $ と $ (0, 2, 1) $ の $ 2 $ つです．したがって，各クエリの答えは以下のように求まります． - $ 1 $ つ目のクエリの答えは $ \mathrm{mex}(\lbrace 0\rbrace)+\mathrm{mex}(\lbrace 0\rbrace)=1+1=2 $ です． - $ 2 $ つ目のクエリの答えは $ \mathrm{mex}(\lbrace 1\rbrace)+\mathrm{mex}(\lbrace 2\rbrace)=0+0=0 $ です． - $ 3 $ つ目のクエリの答えは $ \mathrm{mex}(\lbrace 0,1\rbrace)+\mathrm{mex}(\lbrace 0,2\rbrace)=2+1=3 $ です． - $ 4 $ つ目のクエリの答えは $ \mathrm{mex}(\lbrace 0,1,2\rbrace)+\mathrm{mex}(\lbrace 0,2,1\rbrace)=3+3=6 $ です． ### Constraints - $ 1\leq N\leq 5000 $ - $ 1\leq Q\leq 5\times 10^5 $ - $ -1\leq A_i\leq N-1 $ - $ 1\leq i\lt j\leq N $ に対し， $ A_i\neq -1 $ かつ $ A_j\neq -1 $ ならば $ A_i\neq A_j $ - 各クエリにおいて， $ 1\leq l\leq r\leq N $ - 入力は全て整数