题目内容

推理集群上排着 $m$ 项作业，第 $p$ 项有一个收益 $v_p$（正数表示划算，负数表示亏本）。

调度允许开一次加速窗口：挑一段连续作业 $[L,R]$（$1\le L\le R\le m$），把这段里每一项的收益改成原来的两倍。也可以一次都不开。

窗口用完之后（或者根本没用），再从作业序列里取出一段非空的连续作业，使它们的收益加起来尽量大。请给出这个最大和。

取出的那段至少要包含一项，不能交空段。

输入描述

首行给出正整数 $k$（$1\le k\le 2\times 10^{1}$），即询问组数。

随后 $k$ 行，每行先写出正整数 $m$（$1\le m\le 2\times 10^{5}$），再跟 $m$ 个整数 $v_1,v_2,\dots,v_m$（$|v_p|\le 1000000000$），即该组作业条数和各项收益。

各组 $m$ 加起来不超过 $200000$。

输出描述

一行输出 $k$ 个整数，相邻两项用空格隔开，依次为每组询问的最大连续收益和。

样例1

输入

2
4 2 -3 4 -1
3 -5 -2 -7

输出

8 -2

说明

• 第一组：把 $[3,3]$（收益 $4$）翻倍，序列变成 $2,-3,8,-1$。最大连续和是单独的 $8$。
• 第二组：全是负数，翻倍只会更亏，不开窗口，答案是最大的一项 $-2$。

样例2

输入

1
6 1 2 -5 3 -1 4

输出

12

说明

把 $[4,6]$（$3,-1,4$）翻倍，这段和从 $6$ 变成 $12$。左侧 $1,2,-5$ 接上去会变差，所以最大就是 $12$。