tourist vs rainboy

$N$개의 문제가 난이도 오름차순으로 배치되어 있다. $i$번 문제를 해결하는 데에는 $A_i$만큼의 시간이 걸리며,

을 만족한다.

tourist와 rainboy는 모두 시간 $0$에 문제 풀이를 시작한다. 두 사람은 한 번에 한 문제만 해결하며, 문제 사이에 쉬지 않는다. 어떤 문제의 해결 시각은 문제 풀이를 시작한 시점부터 그 문제를 해결할 때까지 지난 누적 시간이다. 한 사람의 페널티는 모든 문제의 해결 시각의 합이다.

tourist는 $1,2,\cdots,N$번 문제 순서로 해결한다. rainboy는 $N,N-1,\cdots,1$번 문제 순서로 해결한다. 두 사람 모두 모든 문제를 해결한다.

rainboy의 페널티에서 tourist의 페널티를 뺀 값을 구하여라.

입력은 다음과 같은 형식으로 주어진다.

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

각 케이스는 다음과 같은 형식으로 주어진다.

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

각 테스트 케이스마다 rainboy의 페널티에서 tourist의 페널티를 뺀 값을 한 줄에 출력한다.

• $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$).
• 모든 테스트 케이스에 대한 $N$의 합은 $200\,000$ 이하이다.