题目描述

给定一个长度为 $n$ 的整数数组 $a_1,a_2,\ldots,a_n$。

一个数组的价值定义为它所有前缀最大值之和：

例如，数组 $[1,2,1]$ 的价值为 $\max(1)+\max(1,2)+\max(1,2,1)=1+2+2=5$。

你可以选择两个下标 $i,j$，交换 $a_i$ 和 $a_j$。该操作最多执行一次。

请求出操作后数组可能达到的最大价值。

输入格式

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

每组测试数据第一行包含一个整数 $n$，表示数组长度。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

输出格式

对于每组测试数据，输出操作后数组可能达到的最大价值。

样例

4
5
2 1 4 5 3
2
5 1
3
3 2 1
2
6 7

25
10
9
14

样例说明

第一组测试数据中，可以交换 $a_1$ 与 $a_4$，得到 $[5,1,4,2,3]$，价值为 $5+5+5+5+5=25$。

第二组测试数据中，不交换时价值为 $10$；交换后数组变为 $[1,5]$，价值为 $6$，因此最优是不交换。

数据范围

• $1 \le t \le 100$
• $2 \le n \le 50$
• $1 \le a_i \le 10^4$

来源

Codeforces Round 1074 (Div. 4), Problem B - Prefix Max