E. Вероятностная карточная игра
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Алисы и Боба есть колода из карт, изначально пустая. Они играют в игру, которая длится $$$m$$$ раундов. На $$$i$$$-м раунде происходит следующее:

  • в колоду добавляется карта со значением $$$a_i$$$ (гарантируется, что карты с таким значением раньше в колоде не было);
  • если в колоде меньше $$$3$$$ карт, то раунд завершается;
  • иначе Алиса выбирает себе карту из колоды;
  • потом Боб выбирает себе карту (зная, какую выбрала Алиса; при этом он не может выбрать ту же самую);
  • из оставшихся $$$i-2$$$ карт выбирается еще одна равновероятно;
  • в конце все три выбранные карты возвращаются в колоду.

Пусть $$$a$$$ — число на карте Алисы, $$$b$$$ — число на карте Боба, $$$c$$$ — число на случайной из оставшихся. Тогда Боб получает:

  • $$$0$$$ очков, если $$$|a - c| \le |b - c|$$$ (где $$$|x|$$$ означает абсолютную величину $$$x$$$);
  • $$$0$$$ очков, если карта $$$c$$$ находится между картами $$$a$$$ и $$$b$$$ (то есть $$$a \lt c \lt b$$$ или $$$b \lt c \lt a$$$);
  • $$$|b-c|$$$ очков в противном случае.

Цель Алисы в каждом раунде — минимизировать математическое ожидание очков Боба, цель Боба — его максимизировать. Какое будет матожидание очков Боба в каждом раунде при оптимальной игре обоих игроков? Выведите математическое ожидание по модулю $$$998\,244\,353$$$.

Обратите внимание, что игроки минимизируют или максимизируют вещественное значение математического ожидания, а не его представление по модулю $$$998\,244\,353$$$.

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

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

Во второй строке записаны $$$m$$$ целых чисел $$$a_1, a_2, \dots, a_m$$$ ($$$1 \le a_i \le 10^{12}$$$; все $$$a_i$$$ различны).

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

Выведите $$$m-2$$$ целых чисел: $$$i$$$-е число должно быть равно математическому ожиданию очков Боба в $$$i+2$$$ раунде при оптимальной игре обоих игроков по модулю $$$998\,244\,353$$$ (т. е. пусть математическое ожидание равно несократимой дроби $$$\frac{x}{y}$$$; вам нужно вывести $$$x \cdot y^{-1} \bmod 998\,244\,353$$$, где $$$y^{-1}$$$ — это такое число, что $$$y \cdot y^{-1} \bmod 998\,244\,353 = 1$$$).

Обратите внимание, что игроки минимизируют или максимизируют вещественное значение математического ожидания, а не его представление по модулю $$$998\,244\,353$$$.

Примеры
Входные данные
5
1 10 3 11 7
Выходные данные
0
499122177
665496236
Входные данные
6
23 7 11 24 10 28
Выходные данные
0
499122177
1
748683266
Входные данные
9
4 10 7 1 16 5 9 12 2
Выходные данные
0
499122178
2
499122178
798595484
831870296
427819010
Примечание

В первом примере ответы: $$$0, \frac{1}{2}, \frac{2}{3}$$$.

Во втором примере ответы: $$$0, \frac{1}{2}, 1, \frac{5}{4}$$$.

В третьем примере ответы: $$$0, \frac{3}{2}, 2, \frac{3}{2}, \frac{8}{5}, \frac{11}{6}, \frac{11}{7}$$$.