UOJ Logo Zijian Online Judge

ZOJ

Statistics

你有一个长度为$n$的序列$a_1,a_2...a_n$。你可以进行无限次如下操作:选择一个$i\in [2,n-1]$,使$$a_{i-1}=a_{i-1}+a_i$$ $$a_{i+1}=a_{i+1}+a_i$$ $$a_i=-a_i$$

你需要最小化$$max_{i=1}^{n}|a_i|$$

输入格式

输入包含多组数据。

第一行一个正整数$T$表示数据组数。

对于每组数据。

第一行一个正整数$n$。

接下来一行$n$个数$a_1,a_2....a_n$。

输出格式

一共$T$行。

每行一个整数$ans$表示这组数据的答案。

样例一

input

3
3
5 -2 3
4
0 0 0 0
3
1 2 3

output

3
0
3

explanation

对于第一组数据: 对$i=2$进行操作后,$a_1=3$,$a_2=2$,$a_3=1$ 答案为$3$。 对于第二组数据: 不用操作。

样例二

input

3
4
-1 -2 -3 7
4
2 3 4 -8
5
-1 -1 6 -1 -1

output

5
7
4

样例三

见下发文件

限制与约定

本题共有25个测试点,每个测试点4分。

对于全部数据$T\leq 3$,$3\leq n\leq 3\times 10^5$,$|a_i|\leq 10^9$。

具体规模请见下表。

测试点编号$n$$|a_i|$特殊限制
$1$$=3$$\leq 1000$
$2$$\le 5$
$3$
$4$$\le 10$
$5$
$6$
$7$
$8$$\le 20$
$9$
$10$
$11$$\le 100$$\leq 10^9$$a_i \geq 0$
$12$
$13$
$14$
$15$$\le 500$
$16$
$17$$a_i \geq 0$
$18$$\le 5000$
$19$
$20$
$21$$\le 10^5$$a_i \geq 0$
$22$
$23$
$24$$\le 3\times 10^5$
$25$

时间限制:$1\texttt{s}$

空间限制:$512\texttt{MB}$

下载

样例数据下载