A92779.Alice打扰别人睡觉

众所周知，人在睡觉的时候头上会出现一串"Z"字往上飘，而有些人的"Z"居然会往下飘。如果这些"Z"字被人摘走了那那个人就会被吵醒，Alice非常喜欢摘走这些人的"Z"字，然后把这些人吵醒。
大家都趴在一张桌子上睡觉，大家头上"Z"字的飘起高度可以形成一个一维向量数组 $\{ a_0, a_1, a_2, a_3... a_n \}$ ，Alice可以一次性吵醒一个区间 $[ l , r ] (0≤l≤r≤n)$ 内的所有人，这些人对应的向量会被移除这个数组，Alice是一个超级大坏蛋，所以她可以无限次进行这种恶心人的行为，也可以一次都不进行。
Alice怎么这么坏啊！你要写一段程序得到Alice吵醒哪些人之后能让数组留下的向量和的模最大。
(一维向量是‌只有一个分量的向量‌，通常用单个数值表示，其方向由数值的正负号决定（正数表示一个方向，负数表示相反方向），大小（模）为该数值的绝对值。‌‌)

一共 $2n+1$ 行，第 $1$ 行表示有 $n$ ( $2≤n≤500$ )组测试用例。
接下来每 $2$ 行是一个测试用例
每个测试的第 $1$ 行有 $1$ 个数 $size$ ( $1≤size≤500$ )，$size$ 表示这个桌子上有几个人在睡觉。
第 $2$ 行有 $size$ 个数，表示这些人的"Z"会飘多高的一维向量数组。( $-1⋅10^5≤一维向量≤1⋅10^5$ )

对于每组测试数据，新起一行，共 $n$ 行。
每一行输出一个整数代表Alice这么做后的最大的向量和的模。

对于第一组测试数据，把区间 $[2, 3]$ 的人叫醒，得到新数组的向量和的模为 $7$ ，此时是向量和的模长最大的。
对于第二组测试数据，把区间 $[0, 1]$ 和 $[3, 5]$ 的人叫醒，得到新数组的向量和的模为 $11$ ，此时是向量和的模长最大的。