5350：MZL's munhaff function

MZL is a mysterious mathematician, and he proposed a mysterious function at his young age.
Stilwell is very confused about this function, and he need your help.
First of all, given $n$ positive integers $A_i$ and $A_i\geq A_{i+1}$.
Then, generate $n$ positive integers $B_i$
$$B_i=\sum_{j=i}^nA_j$$
Define $f(i,j)$ for $i,j\in Z$
$$
f(i,j)=\left\{\begin{matrix}
0 & & (i,j)=(1,1)\\
min(f(i-1,j+1),f(i,\lceil\frac{j}{2}\rceil)+B_i) & & i,j\in[1,n],~(i,j)\neq(1,1) \\
10^{11037} & & otherwise
\end{matrix}\right.
$$
Find $f(n,1)$.

The first line of the input contains a single number $T$, the number of test cases.
For each test case, the first line contains a positive integer $n$, and the next line contains $n$ positive integers $A_i$.
$T\leq 100$, $1\leq n\leq 10^5$, $\sum n\leq 10^6$, $1\leq A_i\leq 10^4$.

For each test case, output $f(n,1)$ in a line.