Long Long (Codeforces 1843B)
Tags: Math, two pointers

Today Alex was brought array $$$a_1, a_2, \dots, a_n$$$ 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 \leq l \leq r \leq n$$$, and multiply all elements of the array from $$$l$$$ to $$$r$$$ inclusive by $$$-1$$$. In other words, Alex can replace the subarray $$$[a_l, a_{l + 1}, \dots, a_r]$$$ by $$$[-a_l, -a_{l + 1}, \dots, -a_r]$$$ 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 \leq t \leq 10^4$$$) — number of test cases. Then the descriptions of the test cases follow.The first line of each test case contains one integer $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — length of the array.The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$-10^9 \leq a_i \leq 10^9$$$) — elements of the array.It is guaranteed that the sum of $$$n$$$ for all test cases does not exceed $$$2 \cdot 10^5$$$.

Output: For each test case output two space-separated numbers: the maximum possible sum of numbers in the array and the minimum number of operations to get this sum.Pay attention that an answer may not fit in a standard integer type, so do not forget to use 64-bit integer type.

Note: Below, for each test case, only one of the possible shortest sequences of operations is provided among many. There are others that have the same length and lead to the maximum sum of elements.In the first test case, Alex can make operations: $$$(1, 4)$$$, $$$(2, 2)$$$, $$$(6, 6)$$$.In the second test case, to get the largest sum you need to make operations: $$$(1, 8)$$$, $$$(5, 6)$$$.In the fourth test case, it is necessary to make only one operation: $$$(2, 3)$$$.

Sample Inputs:
5
6
-1 7 -4 -2 5 -8
8
-1 0 0 -2 1 0 -3 0
5
2 -1 0 -3 -7
5
0 -17 0 1 0
4
-1 0 -2 -1

Sample Outputs:
27 3
7 2
13 1
18 1
4 1

Solution (Python):
for s in [*open(0)][2::2]:
    t = r = 0
    d = 1
    for x in map(int, s.split()):
        if x < 0:
            t -= x
            r += d
            d = 0
        if x > 0:
            t += x
            d = 1
    print(t, r)

Solution (Python):
for s in [*open(0)][2::2]:
    t = r = 0
    d = 1
    for x in map(int, s.split()):
        if x < 0:
            t -= x
            r += d
            d = 0
        if x > 0:
            t += x
            d = 1
    print(t, r)

Solution (Python):
import bisect
from sys import stdin
input = stdin.readline
mod = 10 ** 9 + 7
eps = 10 ** (-9)

def linp(type=int):
    return list(map(type, input().split()))

def minp(type=int):
    return map(type, input().split())

def tinp(type=int):
    return type(input())

def __gcd(a, b):
    return a if b == 0 else __gcd(b, a % b)

def __lcm(a, b):
    return a * b / __gcd(a, b)

def __fact(n):
    return 1 if n == 1 else n * __fact(n - 1)

def __mex(a):
    mex = 0
    a.sort()
    for x in a:
        if x <= mex:
            mex += 1
        else:
            break
    return mex

def __dist(x1, y1, x2, y2):
    return (x1 - x2) ** 2 + (y1 - y2) ** 2

def __getprimes(n):
    isprime = [True for i in range(n + 1)]
    primes = []
    for i in range(2, n + 1):
        if isprime[i]:
            for j in range(i * i, n + 1, i):
                isprime[j] = False
    for i in range(2, n + 1):
        if isprime[i]:
            primes.append(i)
    return primes

def __getdividers(n):
    i = 1
    ret = []
    while i * i <= n:
        if n % i == 0:
            ret.append(i)
            if i * i != n:
                ret.append(n // i)
        i += 1
    ret.sort()
    return ret

def __modInverse(a, m):
    m0 = m
    y = 0
    x = 1
    if m == 1:
        return 0
    while a > 1:
        q = a // m
        t = m
        m = a % m
        a = t
        t = y
        y = x - q * y
        x = t
    if x < 0:
        x = x + m0
    return x

def __isprime(n):
    if n < 2:
        return False
    i = 2
    while i * i <= n:
        if n % i == 0:
            return False
        i += 1
    return True

def __cntprimediv(n):
    ret = 0
    x = n
    i = 2
    while i * i <= x:
        while n % i == 0:
            n //= i
            ret += 1
        i += 1
    if n > 1:
        ret += 1
    return ret

def __primefactors(n):
    ret = []
    x = n
    i = 2
    while i * i <= x:
        while n % i == 0:
            ret.append(i)
            n //= i
        i += 1
    if n > 1:
        ret.append(n)
    return ret

def __sumdigit(n):
    ret = 0
    while n > 0:
        ret += n % 10
        n //= 10
    return ret

def __zfunc(s):
    n = len(s)
    z = [0 for i in range(n)]
    l = 0
    r = 0
    for i in range(1, n):
        if r >= i:
            z[i] = min(z[i - l], r - i + 1)
        while z[i] + i < n and s[z[i]] == s[z[i] + i]:
            z[i] += 1
        if i + z[i] - 1 > r:
            l = i
            r = i + z[i] - 1
    return z

def __to(n, x):
    ret = ''
    while n > 0:
        q = n % x
        if q < 10:
            ret += str(q)
        else:
            ret += chr(q - 10 + ord('a'))
        n //= x
    return ret[::-1]

def solve(t_id):
    n = tinp()
    a = linp()
    sum = 0
    cnt = 0
    has = False
    for x in a:
        sum += abs(x)
        if x > 0:
            if has:
                cnt += 1
            has = False
        if x < 0:
            has = True
    if has:
        cnt += 1
    print(sum, cnt)
tc = 1
tc = int(input())
for i in range(tc):
    solve(i + 1)