Background

My reflection brightest sunlight

Ran too far forgot my name

Falling tears still shine like dreams

Turning the pain to brighter days

Even if I lose my way

As feelings fade they stay the same

May be beaten when I'm broken

But I know I'm still shining

——Mayonazy "Still Shining".

Problem Description

Given an array $a$ of length $n$.

For a permutation $p$ of $1 \sim n$, define $t(p)=\displaystyle\sum_{i=1}^{n}\sum_{j=\min(p_i,p_{i-1})}^{\max(p_i,p_{i-1})}a_j$. In particular, let $p_0=p_n$.

Let $S$ be the set of all permutations of length $n$. Find $g(a)=\displaystyle\min_{p \in S}\ t(p)$.

Input Format

This problem contains multiple test cases.

The first line contains a positive integer $T$, the number of test cases.

For each test case:

The first line contains a positive integer $n$.

The second line contains $n$ integers $a_i$.

Output Format

Output $T$ lines, each containing one integer, which is the value of $g(a)$.

2
3
1 -2 3
66
-70 68 -92 74 52 53 -5 -94 1 68 -42 -14 25 6 51 -98 -72 94 -69 -3 -13 75 29 62 74 -33 -3 -32 75 29 -2 -79 -99 -81 14 42 92 -28 -67 -40 -96 35 8 -5 83 -81 5 95 -71 78 54 55 -77 6 71 18 71 -15 -74 98 69 -36 18 -33 10 -79

2
-5788

Hint

[Sample Explanation]

For the first test case, you can construct the permutation $p=[1,2,3]$.

[Constraints]

This problem uses bundled testdata.

For $100\%$ of the testdata, it is guaranteed that $1 \le T \le 10^4$, $1 \le n \le 2\times10^5$, $\sum n \le 2\times10^6$, and $|a_i|\le10^9$.

Translated by ChatGPT 5