AT_arc216_b [ARC216B] Range Mex Sum

You are given a positive integer $ N $ and a sequence of integers $ A = (A_1, A_2, \ldots, A_N) $ . Each $ A_i $ satisfies $ -1 \leq A_i \leq N-1 $ , and for $ 1 \leq i < j \leq N $ , if $ A_i \neq -1 $ and $ A_j \neq -1 $ , then $ A_i \neq A_j $ . Answer the following query $ Q $ times. - You are given integers $ l, r\ (1 \leq l \leq r \leq N) $ . Find the sum, modulo $ 998244353 $ , of $ \mathrm{mex}(\lbrace P_l, P_{l+1}, \ldots, P_r \rbrace) $ over all permutations $ P = (P_1, P_2, \ldots, P_N) $ of $ (0, 1, \ldots, N-1) $ satisfying $ A_i \neq -1 \implies P_i = A_i $ . What is $ \mathrm{mex}(S) $ ? For a set $ S $ of non-negative integers, $ \mathrm{mex}(S) $ is defined as the smallest non-negative integer not contained in $ S $ .

The input is given from Standard Input in the following format: > $ N $ $ Q $ $ A_1 $ $ A_2 $ $ \ldots $ $ A_N $ $ \mathrm{query}_1 $ $ \mathrm{query}_2 $ $ \vdots $ $ \mathrm{query}_Q $ Each query is given in the following format: > $ l $ $ r $

Output $ Q $ lines. The $ i $ -th line should contain the answer to $ \mathrm{query}_i $ .

### Sample Explanation 1 The permutations $ P $ satisfying $ A_i \neq -1 \implies P_i = A_i $ are $ (0, 1, 2) $ and $ (0, 2, 1) $ . Thus, the answer to each query is computed as follows. - The answer to the first query is $ \mathrm{mex}(\lbrace 0 \rbrace) + \mathrm{mex}(\lbrace 0 \rbrace) = 1 + 1 = 2 $ . - The answer to the second query is $ \mathrm{mex}(\lbrace 1 \rbrace) + \mathrm{mex}(\lbrace 2 \rbrace) = 0 + 0 = 0 $ . - The answer to the third query is $ \mathrm{mex}(\lbrace 0, 1 \rbrace) + \mathrm{mex}(\lbrace 0, 2 \rbrace) = 2 + 1 = 3 $ . - The answer to the fourth query is $ \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 $ - For $ 1 \leq i < j \leq N $ , if $ A_i \neq -1 $ and $ A_j \neq -1 $ , then $ A_i \neq A_j $ . - For each query, $ 1 \leq l \leq r \leq N $ . - All input values are integers.