区间dp,dp[i][j][0/1]表示上一个数选择区间最左边/最右边。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod = 998244353;
const int maxn = 1e3 + 10;
int dp[maxn][maxn][2];
int a[maxn];
int n;
int qpow(int a,int b)
{
if(a == 0 && b == 0)return 0;
int res = 1;
while(b)
{
if(b & 1)res = res * a % mod;
a = a * a % mod;
b >>= 1;
}
return res;
}
void solve()
{
memset(dp,0,sizeof(dp));
cin >> n;
for(int i = 1;i <= n;i++)cin >> a[i];
for(int len = 1;len < n;len++)
{
for(int i = 1;i + len <= n;i++)
{
int j = i + len;
dp[i][j][0] = max(dp[i + 1][j][1] + qpow(a[i],a[j]),dp[i + 1][j][0] + qpow(a[i],a[i + 1])) % mod;
dp[i][j][1] = max(dp[i][j - 1][0] + qpow(a[j],a[i]),dp[i][j - 1][1] + qpow(a[j],a[j - 1])) % mod;
}
}
cout << max(dp[1][n][0],dp[1][n][1]) << '\n';
}
signed main()
{
int T;
cin >> T;
while(T--)solve();
return 0;
}