Optimal Deque Removal for Maximum Score

Fusu has a double‐ended queue \( a \) containing \( n \) numbers. This deque is similar to the conventional queue in computer science, but it supports both removals from the head and from the tail. Fusu will perform exactly \( n \) operations to construct a sequence \( b \) of length \( n \) by using one of the following two operations at each step \( i \) (\( 1 \le i \le n \)):

1. Set \( b_i \) to the element at the head of \( a \) and then pop the head element from \( a \).
2. Set \( b_i \) to the element at the tail of \( a \) and then pop the tail element from \( a \).

For any pair \( (i,j) \), we define its score as follows:

[ \mathrm{score}(i,j) = i^j \bmod 998244353 ]

with the special definition \( 0^0 = 0 \). The final objective is to choose an optimal sequence of removals that maximizes the sum:

[ S = \sum_{i=1}^{n-1} \mathrm{score}(b_i, b_{i+1}) ]

Note that only the computation of each pair \( \mathrm{score}(b_i, b_{i+1}) \) is taken modulo \( 998244353 \); the overall sum is not reduced modulo any number.

Observation: Every valid removal strategy produces a sequence \( b \) that can be described by an integer \( k \) (with \( 0 \le k \le n \)). If we choose to remove exactly \( k \) elements consecutively from the head at the beginning, then the resulting sequence \( b \) is:

• For \( k = 0 \): \( b = [a_n, a_{n-1}, \dots, a_1] \) (i.e. the reverse of \( a \)).
• For \( 0 < k < n \): \( b = [a_1, a_2, \dots, a_k, a_n, a_{n-1}, \dots, a_{k+1}] \).
• For \( k = n \): \( b = [a_1, a_2, \dots, a_n] \) (i.e. the original order).

Using this observation, the problem reduces to choosing the optimal \( k \) in \( [0, n] \) to maximize the resulting sum:

• When \( k = 0 \): \( S = \sum_{i=1}^{n-1} \mathrm{score}(a_{n-i+1}, a_{n-i}) \).
• When \( k = n \): \( S = \sum_{i=1}^{n-1} \mathrm{score}(a_i, a_{i+1}) \).
• Otherwise, for \( 0 < k < n \): \[ S = \left(\sum_{i=1}^{k-1}\mathrm{score}(a_i,a_{i+1})\right) + \mathrm{score}(a_k, a_n) + \left(\sum_{j=1}^{n-k-1}\mathrm{score}(a_{n-j+1}, a_{n-j})\right). \]

Your task is to compute the maximum achievable sum \( S \) given the input deque \( a \).

inputFormat

The first line contains an integer \( n \) (\( n \ge 1 \)) representing the number of elements in the deque \( a \).

The second line contains \( n \) space-separated integers \( a_1, a_2, \dots, a_n \), representing the elements of the deque from head to tail.

outputFormat

Output one integer, which is the maximum score sum \( S \) achievable by optimally choosing the removal order.

sample

1
0

0