Longest Contiguous Subarray with Maximum Sum

You are given an array of integers (a_1, a_2, \dots, a_n). Your task is to find the length of the contiguous subarray which has the maximum possible sum. In case there are multiple subarrays with the same maximum sum, you should return the length of the subarray that appears first in the array.

For example, consider the array: ( -2,\ 1,\ -3,\ 4,\ -1,\ 2,\ 1,\ -5,\ 4 ) The contiguous subarray [4, -1, 2, 1] has the maximum sum of 6 and its length is 4, so the output is 4.

inputFormat

The first line of input contains a single integer (n) representing the number of elements in the array. The second line contains (n) space-separated integers (a_1, a_2, \dots, a_n).

outputFormat

Output a single integer which is the length of the contiguous subarray with the maximum sum as per the given criteria.## sample

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

4