H. Сумма MEX
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

MEX последовательности неотрицательных чисел $$$[s_1, s_2, \dots, s_n]$$$ — минимальное неотрицательное целое число, которое не встречается в этой последовательности.

Дан массив $$$[a_1, a_2, \dots, a_n]$$$, где каждый элемент — целое число от $$$-1$$$ до $$$n$$$. Для каждого $$$i$$$ от $$$1$$$ до $$$n$$$ посчитайте $$$f([a_1, a_2, \dots, a_i])$$$, где $$$f(s)$$$ для массива $$$s$$$ определяется следующим образом:

  • рассмотрим все различные массивы $$$s'$$$, которые получаются из массива $$$s$$$ заменой всех элементов, равных $$$-1$$$, на целые числа от $$$0$$$ до $$$n$$$;
  • $$$f(s)$$$ равна сумме MEX всех таких массивов $$$s'$$$.
Входные данные

В первой строке задано одно целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$).

Во второй строке заданы $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$-1 \le a_i \le n$$$).

Дополнительное ограничение на входные данные: в массиве $$$a$$$ не более $$$300$$$ элементов, равных $$$-1$$$.

Выходные данные

Для каждого $$$i$$$ от $$$1$$$ до $$$n$$$ выведите одно целое число — $$$f([a_1, a_2, \dots, a_i])$$$, взятое по модулю $$$998244353$$$.

Примеры
Входные данные
5
-1 1 -1 3 -1
Выходные данные
1 2 24 26 248
Входные данные
7
3 5 -1 -1 -1 -1 1
Выходные данные
0 0 1 17 223 2645 4906
Входные данные
10
3 8 5 1 0 0 7 2 2 8
Выходные данные
0 0 0 0 2 2 2 4 4 4
Примечание

Рассмотрим $$$i=3$$$ в первом примере. Нужно посчитать $$$f([-1, 1, -1])$$$. Существует $$$36$$$ различных массивов, которые можно получить, заменив каждый элемент $$$-1$$$ на целое число от $$$0$$$ до $$$5$$$. Для $$$25$$$ из них (тех, в которых нет $$$0$$$) MEX равен $$$0$$$. Рассмотрим оставшиеся $$$11$$$:

  • MEX массива $$$[0, 1, 0]$$$ равен $$$2$$$;
  • MEX массива $$$[0, 1, 1]$$$ равен $$$2$$$;
  • MEX массива $$$[0, 1, 2]$$$ равен $$$3$$$;
  • MEX массива $$$[0, 1, 3]$$$ равен $$$2$$$;
  • MEX массива $$$[0, 1, 4]$$$ равен $$$2$$$;
  • MEX массива $$$[0, 1, 5]$$$ равен $$$2$$$;
  • MEX массива $$$[1, 1, 0]$$$ равен $$$2$$$;
  • MEX массива $$$[2, 1, 0]$$$ равен $$$3$$$;
  • MEX массива $$$[3, 1, 0]$$$ равен $$$2$$$;
  • MEX массива $$$[4, 1, 0]$$$ равен $$$2$$$;
  • MEX массива $$$[5, 1, 0]$$$ равен $$$2$$$.

Сумма этих значений равна $$$24$$$.

Если рассмотреть $$$i=4$$$, то к каждому из этих массивов надо приписать $$$3$$$. Это увеличит MEX двух массивов на $$$2$$$, поэтому для $$$i=4$$$ ответ равен $$$26$$$.