G. Minimize Sum
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

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.

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

Example
Input
3
2
1 2
5
9 3 6 5 9
8
5 6 4 8 3 1 0 10
Output
0
14
19