Maximum Subarray Sum and Minimum Length

You are given an array A consisting of n integers. Your task is to compute two values:

• The maximum sum S over all contiguous subarrays of A.
• The minimum length L of any contiguous subarray whose sum is S. In other words, if there are several subarrays with sum S, choose the one with the smallest length.

Formally, let a subarray be defined by indices i and j (with 0 \(\le i \le j < n\)) and let its sum be \(\sum_{k=i}^{j}A[k]\). Then

\[ S = \max_{0 \le i \le j < n} \sum_{k=i}^{j} A[k] \]

and if there are multiple subarrays that achieve \(S\), choose one with the minimum length \(L = j - i + 1\).

Example: For A = [-2, 1, -3, 4, -1, 2, 1, -5, 4], the maximum subarray sum is 6 and the shortest subarray achieving this is of length 4 (namely, [4, -1, 2, 1]).

inputFormat

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

1. The first line contains a single integer n, the number of elements in the array.
2. The second line contains n space-separated integers representing the elements of the array A.

outputFormat

Print two integers to standard output (stdout) separated by a space:

• S: the maximum subarray sum.
• L: the minimum length of a contiguous subarray that achieves the sum S.

## sample

9
-2 1 -3 4 -1 2 1 -5 4

6 4

</p>