[yLCPC2024] D. 排卡

题目描述

有一个双端队列，队列中从左到右有 $n$ 张卡牌，第 $i$ 张卡牌上的数字是 $a_i$。

你需要把所有卡牌依次取出，形成新的序列 $b$。每次只能取出当前队首或队尾的卡牌，并把它接到序列 $b$ 的末尾。

相邻两张卡牌 $i,j$ 的得分为 $i^j\bmod 998244353$。特别地，$0^0$ 的得分规定为 $0$。序列的总得分是所有相邻卡牌得分之和，总和本身不再取模。

请计算能够得到的最大总得分。

输入格式

第一行一个整数 $T$，表示测试数据组数。

每组数据第一行一个整数 $n$，第二行 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

输出格式

对每组数据输出一行一个整数，表示最大总得分。

样例输入

3
2
0 0
3
1 2 3
4
2 1 2 1

样例输出

0
11
7

数据范围与约定

$1\le T$，$2\le n\le 1000$，$0\le a_i<998244353$，所有测试数据中 $n$ 的总和不超过 $1000$。

题目来源：洛谷 P10236