Migrated from Lutece 1923 中堂系的困难任务

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

为了考察三澄美琴的聪明程度，中堂系给三澄美琴出了一道题

给定 $n$ 个整数 $A_i$ ，可以确定 $n$ 个 $B_i=\sum_{j=i}^n A_j$。

$$f(i,j)= \begin{cases} 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{cases} $$

求 $f(n,1)$。

Input

共有$t$组数据 $t\le 100,n\le 1e5$, 总共的$N\le 10^5,1\le A_i\le 10^4$, $A_{i+1} \le A_i$

Output

输出$f(n,1)$

Samples

3
3
1 1 1
5
28 26 25 24 1
10
996 901 413 331 259 241 226 209 139 49

5
233
11037

Resources

2018 UESTC Training for Data Structures