이제 간단한 게임을 해보자. 길이가 $n$인 배열 $A$가 주어질 때, 당신의 임무는 이 배열에서 로봇을 움직이거나 멈추도록 제어하는 것이다.

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

• Stop (멈춤). 이 행동을 선택하면 게임이 즉시 종료된다. 로봇이 위치 $i$에서 멈추면 당신의 점수는 $A_i$가 된다.
• Move (이동). 이 행동을 선택하고 로봇이 위치 $i$에 있다면, 50%의 확률로 로봇은 $i-1$로 이동하고, 나머지 50%의 확률로 $i+1$로 이동한다. 로봇이 위치 $1$이나 $n$에 있을 때는 이 행동을 선택할 수 없다는 점에 유의하라.

두 번째 행동은 로봇이 배열의 양 끝에 있지 않을 때만 선택할 수 있으므로, 어떤 전략을 사용하더라도 $\lim_{m \to +\infty} f(m) = 0$임이 증명 가능하다. 여기서 $f(m)$은 $m$번의 턴이 지난 후에도 게임이 계속될 확률을 나타낸다.

당신의 임무는 게임의 기대 점수를 최대화하는 것이다.

입력

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

출력

최대 기대 점수를 $998\,244\,353$으로 나눈 나머지를 한 줄에 출력한다. 즉, 정답은 기약분수 $P/Q$ 꼴로 나타낼 수 있으며, 여기서 $Q$는 $998\,244\,353$과 서로소이다. 당신은 $(P \cdot Q^{-1}) \pmod{998\,244\,353}$을 출력해야 한다.

예제

입력 1

3
3 1 2

출력 1

499122179

입력 2

6
6 1 2 5 3 4

출력 2

582309211