RCPC Simulare 2023 day 2 | G. Minimize Sum

Sumin likes deques, so his teacher gave him a cool deque game. The game works based on an array $a$, and is played as follows:

1. There will initially be a variable $T = 0$ and a deque containing just the element $0$.
2. Sumin will go through the array elements, starting with the 1st one and ending at the nth one. At the $i^{th}$ element Gigel must choose one of two ways to progress the game:
   • add to T the first element of the deque, then put $a_i$ at the front of the deque (that is $T := T + deque.front(), \ deque.push \ front(a_i)$ )
   • add to T the last element of the deque, then put $a_i$ at the back of the deque (that is $T := T + deque.back(), \ deque.push \ back(a_i)$ )

After the $n^{th}$ element is processed, the score of the game will be equal to the current value of T. Grigoutz wants to minimize this final score T but he is unsure if he received the minimum score that is possible. Can you help him calculate it?

Task

Sumin 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 length of the array.

The second line of each test case contains $n$ integers $a_1, a_2, \dots a_n$ ($0 \leq a_i \leq 10^9$) - the elements of the array.

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$

Examples

stdin

3
2
1 2
5
9 3 6 5 9
8
5 6 4 8 3 1 0 10

stdout

0
14
19

Example description

For the first test case, Sumin will go for the first choice, resulting in $T = 0$ and the deque containing $1 \ 0$. After this, he will go with the second choice, adding $0$ to $T$, and the deque contains $1 \ 0 \ 2$ in this order.
For the second test case, Sumin will go for the first choice, resulting in $T = 0$ and the deque containing $9 \ 0$. After this, he will go with the second choice, adding $0$ to $T$, and the deque contains $9 \ 0 \ 3$ in this order. Third choice is for the back, $T = 3$ and deque is $9 \ 0 \ 3 \ 6$. Next is the back once again, resulting in $T = 9$ and the deque is $9 \ 0 \ 3 \ 6 \ 5$. Final choice is still on the back side of the deque, resulting in $T = 14$ and the deque being $9 \ 0 \ 3 \ 6 \ 5 \ 9$.