Maximum Sum Subarray with At Most One Negative Number

You are given an array of n integers. Your task is to find the maximum possible sum of any contiguous subarray of the array, under the condition that the subarray contains at most one negative number.

Formally, if we denote a contiguous subarray by \(A[i \ldots j]\), then this subarray is valid if and only if the number of elements \(A[k] < 0\) for \(i \le k \le j\) is at most one.

You are required to output the maximum sum over all valid subarrays.

Note: A subarray is a continuous portion of the array.

The problem can be formally represented using the following constraint: Given an array \(a_1, a_2, \dots, a_n\), find \[ \max_{1 \leq i \leq j \leq n \;:\; \#\{k \in [i, j] : a_k < 0\} \le 1} \sum_{t=i}^{j} a_t. \]

inputFormat

The input is read from standard input and consists of two lines:

1. The first line contains an integer n, which is the number of elements in the array.
2. The second line contains n space-separated integers representing the elements of the array.

outputFormat

Output a single integer which is the maximum sum of a contiguous subarray that contains at most one negative number. The answer should be printed to the standard output.

## sample

5
1 -2 3 4 -1

7

</p>