게임

당신은 지금 간단한 게임을 하고 있다. 길이 $n$인 배열 $A$가 주어질 때, 로봇이 이 배열 안에서 움직이거나 멈추도록 조종해야 한다.

처음에 로봇의 위치는 무작위로 정해진다. 위치 $i \in [1, n]$가 선택될 확률은 $\frac{1}{n}$이다. 각 턴마다 현재 위치를 알고 있으며, 두 가지 행동 중 하나를 결정해야 한다.

• 멈춘다. 이 행동을 선택하면 게임이 즉시 끝난다. 로봇이 위치 $i$에서 멈추면 점수는 $A_i$이다.
• 움직인다. 이 행동을 선택했고 로봇이 위치 $i$에 있다면, $50\%$ 확률로 $i - 1$로 이동하고 나머지 $50\%$ 확률로 $i + 1$로 이동한다. 로봇이 위치 $1$ 또는 $n$에 있을 때는 이 행동을 선택할 수 없다.

두 번째 행동은 로봇이 배열의 양 끝에 있지 않을 때만 선택할 수 있으므로, 어떤 전략을 쓰더라도 $\lim\limits_{m \rightarrow +\infty} f(m) = 0$임을 증명할 수 있다. 여기서 $f(m)$은 $m$턴이 지난 뒤에도 게임이 계속될 확률이다.

당신의 목표는 게임의 기대 점수를 최대로 만드는 것이다.

첫 번째 줄에 정수 $n$이 주어진다 ($1 \le n \le 5 \cdot 10^5$).

두 번째 줄에 $n$개의 정수 $A_1, A_2, \ldots, A_n$이 주어진다 ($1 \le A_i \le 10^{12}$).

가능한 최대 기대 점수를 $998\,244\,353$으로 나눈 나머지를 한 줄에 출력한다. 다시 말해, 답이 $998\,244\,353$과 서로소인 $Q$에 대해 유리수 $P / Q$로 표현된다고 할 때, $(P \cdot Q^{-1}) \bmod 998\,244\,353$을 출력해야 한다.