#628 Replacement

Statement

Statement language

You are given a sequence $P_1, P_2, \ldots, P_N$ consisting of $N$ integers. Find the minimum possible total cost of performing the following operation exactly $N-1$ times so that only one element remains.

Choose two adjacent elements in the current sequence. Let their values be $x$ and $y$ .
Replace these two elements with a single element whose value is $\min(x,y)$ . The relative order of all other elements remains unchanged.
The cost of this operation is $\max(x,y)$ .

Input

The input is given in the following format.

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$

Output

For each test case, print the minimum total cost on its own line, in input order.

Constraints

$1\leq T\leq50\ 000$ .
$2\leq N\leq100\ 000$ .
$- 10^{9} \leq$ ().

Subtasks

#	Score	Constraints
1	11	$N\leq8$ . The sum of $N$ over all test cases is at most $200$ .
2	31	$P_i\leq P_{i+1}$ for .

Samples

Sample 1

Input

Output

9
-6
7

In the first test case, merging $4,2$ costs $4$ and leaves $(2,5)$ . The next merge costs $5$ , for a total of $9$ . Starting with the last pair gives the same total. In the second case, merging from the left costs and then , totaling . The third case needs one operation: one copy of remains and the cost is .