题目描述

有 \(n\) 个点从左到右排成一行，编号为 \(1, 2, \dots, n\)。第 \(i\) 个点有一个权值 \(a_i\)。如果新建一条点 \(i\) 与点 \(j\) 之间的无向边（\(i < j\)），那么这条边的代价定义为它们中点位置处的权值：

如果 \(\frac{i+j}{2}\) 是整数，那么边 \(i, j\) 的代价为 \(a_{\frac{i+j}{2}}\)；

如果 \(\frac{i+j}{2}\) 不是整数，那么边 \(i, j\) 的代价为中点相邻两个位置的权值平均值，即

\[ \frac{a_{\lfloor (i+j)/2 \rfloor} + a_{\lceil (i+j)/2 \rceil}}{2}. \]

现在你可以在这些点之间任意新建边，要求最终所有点连通。请你求出使图连通的最小总代价的 \(2\) 倍。

题目有多组数据。

约束： \(1 \le n \le 3000\)， \(1 \le a_i \le 10^9\)。

输入格式

第一行输入一个整数 \(T\)，表示数据组数。保证 \(T = 5\)。

对于每组数据：

• 第一行输入一个整数 \(n\)，表示点的数量。
• 第二行输入 \(n\) 个整数 \(a_1, a_2, \dots, a_n\)，表示每个点的权值。

输出格式

对于每组数据，输出一行一个数，表示让所有点连通的最小总代价的 \(2\) 倍。

样例输入

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

样例输出

0
8
8
36
64