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

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

Sum of MEX

Examples