题目描述

天下的 RP 是守恒的，我们的 RP 总是在高高低低中不断变化。小亮决定在期末考试前多多积累 RP。他做的每件事情对 RP 有如下影响：他做了的第一件事情是涨 RP 的；如果他做的上一件事情是涨 RP 的，那么他做的下一件事情是降 RP 的；反之亦然。

小亮现在的 RP 是 \(0\)，在期末考试前有 \(N\) 件事情可以做，每件事情都有自己的 RP 系数。对于这些事情，他可以做或不做。但事情的先后顺序是一定的，也就是说小亮只可以按照给定好的顺序选择做不做该事情。现在请你帮助小亮在期末考试之前，积攒到最多的 RP。

格式

输入格式

第一行为正整数 \(t(≤5)\)，表示 \(t\) 组数据；每组数据中，第一行为一个正整数 \(n(≤5×10^5)\)，代表有 \(n\) 件事情；第二行为 \(n\) 个正整数，代表每件事情的 RP 值 \(R_i(≤10^6)\)。

输出格式

仅包含一个整数,即小亮在期末前能积攒的最大 RP 值。

样例1

输入样例1

2
1
1
4
1 3 1 2

输出样例1

1
4

样例解释

样例 \(1.2\) 中，依次做第 \(2、3、4\) 件事，则 RP 值：\(+3,-1,+2\)，最后的 RP 值是 \(+4\)。

来源

地址：芜湖市二十七中电脑班刷题课
作者：汪老师
模拟赛\(T4\)

文件IO

freopen("const.in","r",stdin);
freopen("const.out","w",stdout);