무작위로 이동하기

배열 위에서 다음 게임을 생각해 봅시다.

당신은 포인터입니다. 처음에는 배열의 원소 하나를 가리키며, 모든 원소가 같은 확률로 선택됩니다.

게임의 매 순간 다음 중 하나를 할 수 있습니다.

1. 게임 종료. 게임이 끝나고, 점수는 가리키고 있는 원소의 값입니다.
2. 이동. 왼쪽 또는 오른쪽 인접 원소로 각각 같은 확률로 이동합니다. 이동한 뒤 배열의 범위를 벗어날 수 있다면 이 선택지는 고를 수 없습니다. (역참조되어 염소로 변할 수도 있고, 게임 전체가 최적화로 사라질 수도 있습니다. 정의되지 않은 동작이라 무슨 일이 일어날지 알 수 없습니다. 어느 쪽도 원하지 않을 것입니다.)

이 선택을 게임이 끝날 때까지 반복합니다. $\lim_{m \to \infty} f(m) = 0$임을 증명할 수 있습니다. 여기서 $f(m)$은 이동을 $m$번 선택할 수 있는 확률입니다.

배열의 점수는 최적으로 플레이할 때 얻을 수 있는 기대 점수의 최댓값입니다. (당신은 똑똑한 포인터입니다.)

배열 $a$가 주어집니다. 각 접두사에 대해 점수를 998244353으로 나눈 나머지를 구하세요.

정수가 아닐 수도 있는 수 $X$를 $M$으로 나눈 나머지는 다음과 같이 정의합니다. 심사위원은 $X$가 어떤 기약분수 $\frac{P}{Q}$와 같고, $Q$가 $M$에 대한 역원을 가짐을 보장합니다. 이때 $X$를 $M$으로 나눈 나머지는 $0$ 이상 $M-1$ 이하의 정수 $A$이며, $P - QA$가 $M$으로 나누어떨어집니다. 이러한 $A$는 유일합니다.

첫 줄에 정수 $n$ ($1 \leq n \leq 5 \cdot 10^5$)이 주어집니다. 이는 $a$의 길이입니다.

둘째 줄에 공백으로 구분된 정수 $a_i$ ($1 \leq a_i \leq 10^6$) $n$개가 주어집니다. 이는 $a$의 원소입니다.

$n$개의 정수를 출력하세요. $i$번째 정수는 길이가 $i$인 접두사의 점수를 998244353으로 나눈 나머지입니다.

첫 번째 입력 예제의 길이 3인 접두사, 즉 배열 전체 $[3, 1, 2]$를 생각해 봅시다. 두 번째 원소에서 시작하면 이동하는 것이 최적 전략입니다. 한 번 이동한 뒤에는 더 이상 이동할 수 없습니다. 다른 원소에서 시작하면 이동하지 않습니다.

이때 점수는 $\frac{5}{2}$이며, 998244353으로 나눈 나머지는 499122179입니다.