对于一个序列$b$，如果它的第一个数小于或等于最后一个数，它的"价值"为序列中所有数字的和，否则"价值"为序列中所有数字的和乘以$-1$。

例如，当$b=[1,3,-7,-8]$，因为它的第一个数$1$大于最后一个数$-8$，价值$=(1+3+(-7)+(-8))\cdot(-1)=11\cdot(-1)=-11$。

给出一个序列$a$，你需要把$a$切成若干部分（或者不进行切割），例如，你可以把$a=[1,3,-2,1,2,6]$分成3个部分$[1,3],[-2,1,2],[6]$。注意你不能把$a$中的数字调换次序。

$a$的"珍贵值"为其所有部分的价值之和。你需要找出最大可能的珍贵值。

输入格式

本题有多组测试数据

输入的第一行包含一个正整数$T$，表示数据组数。

接下来包含$T$组数据，每组数据的格式如下：

输入的第一行包含一个正整数$n$，代表序列的长度。

输入的第二行包含$n$个正整数，第i个数代表$a_i$。

输出格式

对于每組數據：输出一行包含一个整数，代表切割序列后可以获得的最大价值总和。

数据范围

对于所有测试数据，保证：
$3 \le n \le 10^5$
$|a_i| \le 10^9$
$T=5$