P17334 "TPOI-2D" Still Shining

> 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".

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)$.

**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 $T$ lines, each containing one integer, which is the value of $g(a)$.

**[Sample Explanation]** For the first test case, you can construct the permutation $p=[1,2,3]$. **[Constraints]** **This problem uses bundled testdata.** |$\text{Subtask}$|Score|Special Property| |:-:|:-:|:-:| |$1$|$15$|$n\le8, T\leq 100$| |$2$|$15$|$a_i>0$| |$3$|$15$|$a_i