tourist vs rainboy

There are $N$ problems arranged in nondecreasing order of difficulty. Solving problem $i$ takes $A_i$ units of time, and

holds.

tourist and rainboy both start solving problems at time $0$. Each person solves only one problem at a time and takes no breaks between problems. The completion time of a problem is the total elapsed time from the start until that problem is solved. A person's penalty is the sum of the completion times of all problems.

tourist solves the problems in the order $1,2,\cdots,N$. rainboy solves them in the order $N,N-1,\cdots,1$. Both solve all problems.

Find rainboy's penalty minus tourist's penalty.

The input is given from Standard Input in the following format:

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$ $\vdots$ $\mathrm{case}_T$

Each case is given in the following format:

$N$ $A_1\ A_2\ \cdots\ A_N$

For each test case, print rainboy's penalty minus tourist's penalty on one line.

• $1 \leq T \leq 10$.
• $1 \leq N \leq 200\,000$.
• $1 \leq A_i \leq 1\,000\,000$ ($1 \leq i \leq N$).
• $A_i \leq A_{i+1}$ ($1 \leq i < N$).
• The sum of $N$ over all test cases does not exceed $200\,000$.