Today Alex was brought array a1,a2,…,an of length n. He can apply as many operations as he wants (including zero operations) to change the array elements.
In 1 operation Alex can choose any l and r such that 1≤l≤r≤n, and multiply all elements of the array from l to r inclusive by −1
. In other words, Alex can replace the subarray [al,al+1,…,ar] by [−al,−al+1,…,−ar] in 1 operation.
(资料图片)
For example, let n=5, the array is [1,−2,0,3,−1], l=2 and r=4, then after the operation the array will be [1,2,0,−3,−1].
Alex is late for school, so you should help him find the maximum possible sum of numbers in the array, which can be obtained by making any number of operations, as well as the minimum number of operations that must be done for this.
Input
The first line contains a single integer t (1≤t≤104) — number of test cases. Then the descriptions of the test cases follow.
The first line of each test case contains one integer n (1≤n≤2⋅105) — length of the array.
The second line contains n integers a1,a2,…,an (−109≤ai≤109) — elements of the array.
It is guaranteed that the sum of n for all test cases does not exceed 2⋅105.
中文：
今天 Alex 被带来了长度为 n 的数组 a1,a2,…,an。 他可以应用任意数量的操作（包括零操作）来更改数组元素。
在 1 次操作中，Alex 可以选择任意 l 和 r，使得 1≤l≤r≤n，并将数组中从 l 到 r 的所有元素乘以 -1
。 换句话说，Alex 可以在 1 次操作中用 [−al,−al+1,…,−ar] 替换子数组 [al,al+1,…,ar]。
例如，令n=5，数组为[1,−2,0,3,−1]，l=2，r=4，则运算后数组为[1,2,0,−3] ，−1]。
亚历克斯上学迟到了，所以你应该帮助他找到数组中可能的最大数字之和（可以通过任意次数的运算获得），以及为此必须完成的最小运算次数。
输入
第一行包含一个整数 t (1≤t≤104) — 测试用例的数量。 然后是测试用例的描述。
每个测试用例的第一行包含一个整数 n (1≤n≤2⋅105) — 数组的长度。
第二行包含 n 个整数 a1,a2,…,an (−109≤ai≤109) — 数组的元素。
保证所有测试用例的 n 之和不超过 2⋅105。
-----------------------------------------------------------------
第一个输出的是数组的绝对值之和，第二个输出的是负数的区间个数，这里面用2个参数去处理，一个是布尔值，一个是累加数字；下面是代码：
关键词：
