Maximum Subarray Sum and Length

Given an array of integers, your task is to find the contiguous subarray which has the largest sum and then output both the maximum sum and the length of that subarray. Formally, for an array \(a_1, a_2, \ldots, a_n\), find indices \(i\) and \(j\) (with \(1 \le i \le j \le n\)) that maximize the sum \(S = \sum_{k=i}^{j}a_k\). If there exist multiple subarrays with the same maximum sum, choose the one with the longest length.

Example: For the array [-2, 1, -3, 4, -1, 2, 1, -5, 4], the maximum sum is 6 and the subarray achieving this sum has a length of 4.

inputFormat

The first line contains an integer \(n\) representing the number of elements in the array. The second line contains \(n\) space-separated integers denoting the elements of the array.

outputFormat

Output two space-separated integers: the maximum contiguous subarray sum and the length of that subarray.

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

6 4