CF2199H Sum of MEX

The MEX of a sequence of non-negative integers $ [s_1, s_2, \dots, s_n] $ is the smallest non-negative integer that does not appear in this sequence. Given an array $ [a_1, a_2, \dots, a_n] $ , where each element is an integer from $ -1 $ to $ n $ . For each $ i $ from $ 1 $ to $ n $ , calculate $ f([a_1, a_2, \dots, a_i]) $ , where $ f(s) $ for an array $ s $ is defined as follows: - consider all distinct arrays $ s' $ that can be obtained from the array $ s $ by replacing all elements equal to $ -1 $ with integers from $ 0 $ to $ n $ ; - $ f(s) $ is the sum of the MEX of all such arrays $ s' $ .

The first line contains a single integer $ n $ ( $ 1 \le n \le 2 \cdot 10^5 $ ). The second line contains $ n $ integers $ a_1, a_2, \dots, a_n $ ( $ -1 \le a_i \le n $ ). An additional constraint on the input: the array $ a $ contains no more than $ 300 $ elements equal to $ -1 $ .

For each $ i $ from $ 1 $ to $ n $ , output a single integer — $ f([a_1, a_2, \dots, a_i]) $ , taken modulo $ 998244353 $ .

Consider $ i=3 $ in the first example. We need to calculate $ f([-1, 1, -1]) $ . There are $ 36 $ different arrays that can be obtained by replacing each element $ -1 $ with an integer from $ 0 $ to $ 5 $ . For $ 25 $ of them (those that do not contain $ 0 $ ), the MEX is $ 0 $ . Let's consider the remaining $ 11 $ : - The MEX of the array $ [0, 1, 0] $ is $ 2 $ ; - The MEX of the array $ [0, 1, 1] $ is $ 2 $ ; - The MEX of the array $ [0, 1, 2] $ is $ 3 $ ; - The MEX of the array $ [0, 1, 3] $ is $ 2 $ ; - The MEX of the array $ [0, 1, 4] $ is $ 2 $ ; - The MEX of the array $ [0, 1, 5] $ is $ 2 $ ; - The MEX of the array $ [1, 1, 0] $ is $ 2 $ ; - The MEX of the array $ [2, 1, 0] $ is $ 3 $ ; - The MEX of the array $ [3, 1, 0] $ is $ 2 $ ; - The MEX of the array $ [4, 1, 0] $ is $ 2 $ ; - The MEX of the array $ [5, 1, 0] $ is $ 2 $ . The sum of these values is $ 24 $ . If we consider $ i=4 $ , then we need to append $ 3 $ to each of these arrays. This will increase the MEX of two arrays by $ 2 $ , so for $ i=4 $ , the answer is $ 26 $ .