Minimize Sum
Description
Grigorutz is a simple man, he doesn't like to do homework. Today, his english teacher decided to test Grigorutz's intelligence by playing a game with him. There are $n$ essays which might be in Grigorutz's homework. Let $a_i$ be the time Grigorutz will spend to write the $i$-th essay (in minutes). The game is played as follows:
1. There will intially be a deque containing the element $0$ and a variable $T = 0$.
2. The teacher will go through the essays from $1$ to $n$. At the $i$-th step, Grigorutz can do one of the two operations:
$a)$ $T := T + deque.front(), \ deque.push$_$front(a_i)$
$b)$ $T := T + deque.back(), \ deque.push$_$back(a_i)$
After the $n$-th element is added to the deque, $T$ will be the amount of time to spend to solve his homework. Obviously, Grigoutz wants to minimze this time. Can you help him do so?
Grigorutz asks you to write a program which given $n$ and the number of minutes to write each of the essays will print the minimum value of $T$ after the $n$ operations.
The first line contains an integer $t$ ($1 \leq t \leq 10^4$) the number of test cases. Then follows the description of the test cases.
The first line contains a single integer $n$ ($1 \leq n \leq 2 \cdot 10^5$) the number of eassys which might be in the homework.
The second line of each test case contains $n$ integers $a_1, a_2, \dots a_n$ ($1 \leq a_i \leq 10^9$) - the time (in minutes) for each of the essays.
It is guaranteed that the sum of the values of $n$ over all test cases does not exceed $2 \cdot 10^5$.
For each test case, you have to print a single integer - the minimum value of $T$
Input
The first line contains an integer $t$ ($1 \leq t \leq 10^4$) the number of test cases. Then follows the description of the test cases.
The first line contains a single integer $n$ ($1 \leq n \leq 2 \cdot 10^5$) the number of eassys which might be in the homework.
The second line of each test case contains $n$ integers $a_1, a_2, \dots a_n$ ($1 \leq a_i \leq 10^9$) - the time (in minutes) for each of the essays.
It is guaranteed that the sum of the values of $n$ over all test cases does not exceed $2 \cdot 10^5$.
Output
For each test case, you have to print a single integer - the minimum value of $T$
3
2
1 2
5
9 3 6 5 9
8
5 6 4 8 3 1 0 10
0
14
19