n = int(input())
a = list(map(int, input().split()))
dp = [0] * (n + 1)
stack = []

for i in range(1, n + 1):
    current = a[i - 1]
    max_abs = abs(current)
    best = dp[i - 1] + max_abs
    start = i

    while stack:
        val, s, b = stack[-1]
        if max_abs >= abs(val):
            stack.pop()
            candidate = b + (max_abs - abs(val)) * (i - s + 1)
            if candidate > best:
                best = candidate
                start = s
        else:
            break

    stack.append((current, start, best))
    dp[i] = best

print(dp[n])