H. Sum of MEX
time limit per test
5 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

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'$$$.
Input

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$$$.

Output

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

Examples
Input
5
-1 1 -1 3 -1
Output
1 2 24 26 248
Input
7
3 5 -1 -1 -1 -1 1
Output
0 0 1 17 223 2645 4906
Input
10
3 8 5 1 0 0 7 2 2 8
Output
0 0 0 0 2 2 2 4 4 4
Note

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$$$.