Greedy Interval Selection Analysis

You are given an integer sequence \(a_1,a_2,\dots,a_n\) (which may contain negative numbers) and a positive integer \(m\). Consider the following greedy algorithm (which is not always correct) for selecting disjoint intervals:

1. Repeat the following process up to \(m\) times:
1. Among all intervals that do not intersect any interval already chosen (note that the empty interval is allowed), choose an interval whose sum of elements is maximum. (If there are several candidates with the same maximum sum, any one of them may be chosen.)
2. If the empty interval is chosen, the process is terminated; that is, the total number of chosen intervals will be less than \(m\).
2. The answer of the algorithm is the sum of the elements in all the nonempty intervals selected.

For a given sequence \(a_1,a_2,\dots,a_n\) (with \(n\) given) and for each \(m\) with \(1\le m\le n\), determine the maximum possible answer and the minimum possible answer that this greedy algorithm might produce, when tie–breaking is resolved arbitrarily.

Note that:

• The maximum subarray in any interval is defined in the usual way. In particular, if all subarrays have non–positive sum, the empty interval (with sum \(0\)) is considered.
• When the maximum subarray sum in the current available region is positive, the empty interval (with sum 0) will never be chosen because it does not maximize the sum.
• The greedy algorithm operates on the current available segments (initially the whole sequence). After choosing an interval \([l, r]\) from one segment, that segment is split into two (possibly empty) segments \([\text{left}, l-1]\) and \([r+1, \text{right}]\) on which the process continues.

For example, consider the sequence [1, -1, 1] (using 1–based indexing):

• The maximum subarray sum over the entire sequence is \(1\), and it can be achieved by the interval \([1,1]\) or \([3,3]\) (or even \([1,3]\) since \(1+(-1)+1=1\)).
• If the algorithm chooses the interval \([1,3]\) in the first step then it stops (since no further non–overlapping subinterval with positive sum exists), yielding an answer of \(1\).
• If instead it chooses \([1,1]\) in the first step then on the remaining segment \([2,3]\) the maximum subarray is \([3,3]\) with sum \(1\), and the total becomes \(1+1=2\). Hence, when \(m\ge2\) the maximum possible answer is \(2\) and the minimum is \(1\); while when \(m=1\) the only possibility is \(1\).

Your task is to compute, for each \(1\le m\le n\), two numbers: the maximum and minimum possible total sum that the greedy algorithm might output.

inputFormat

The first line contains an integer \(n\) (the length of the sequence).
The second line contains \(n\) space–separated integers \(a_1,a_2,\dots,a_n\).

outputFormat

Output \(n\) lines. The \(i\)–th line (for \(1\le i\le n\)) should contain two space–separated integers: the maximum possible answer and the minimum possible answer attainable by the greedy algorithm with at most \(i\) selections (intervals).

sample

3
1 -1 1

1 1
2 1
2 1