Bạn đang chơi một trò chơi đơn giản. Cho một mảng $A$ có độ dài $n$, nhiệm vụ của bạn là điều khiển một robot di chuyển hoặc dừng lại trong mảng này.

Ban đầu, vị trí của robot được chọn ngẫu nhiên: xác suất chọn vị trí $i \in [1, n]$ là $\frac{1}{n}$. Trong mỗi lượt, bạn biết vị trí hiện tại và cần đưa ra quyết định giữa hai lựa chọn hành động:

• Dừng (Stop). Nếu chọn hành động này, trò chơi kết thúc ngay lập tức. Khi robot dừng lại ở vị trí $i$, điểm số của bạn là $A_i$.
• Di chuyển (Move). Nếu chọn hành động này và robot đang ở vị trí $i$, với 50% khả năng, robot sẽ di chuyển đến $i - 1$, và với 50% khả năng còn lại, nó sẽ di chuyển đến $i + 1$. Lưu ý rằng khi robot ở vị trí $1$ hoặc $n$, bạn không thể chọn hành động này.

Vì hành động thứ hai chỉ có thể được chọn khi robot không ở hai đầu của mảng, ta có thể chứng minh rằng, với bất kỳ chiến lược nào, $\lim_{m \to +\infty} f(m) = 0$, trong đó $f(m)$ biểu thị xác suất trò chơi tiếp tục sau $m$ lượt.

Nhiệm vụ của bạn là tối đa hóa điểm số kỳ vọng của trò chơi.

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên duy nhất $n$ ($1 \le n \le 5 \cdot 10^5$). Dòng thứ hai chứa $n$ số nguyên $A_1, A_2, \dots, A_n$ ($1 \le A_i \le 10^{12}$).

Dữ liệu ra

Xuất ra một dòng duy nhất với một số nguyên: điểm số kỳ vọng tối đa có thể đạt được dưới dạng phân số modulo $998\,244\,353$. Nói cách khác, có thể chứng minh rằng câu trả lời có thể được biểu diễn dưới dạng số hữu tỉ $P/Q$ trong đó $Q$ nguyên tố cùng nhau với $998\,244\,353$, và bạn phải xuất ra $(P \cdot Q^{-1}) \pmod{998\,244\,353}$.

Ví dụ

Ví dụ 1

3
3 1 2

499122179

Ví dụ 2

6
6 1 2 5 3 4

582309211