Longest Maximum Sum Subarray

Given an array of integers, find the contiguous subarray that produces the largest sum. In case there are several subarrays with the same maximum sum, choose the one which has the longest length (the one that appears first in the array). The sum of a subarray is defined as

where (l) and (r) are the starting and ending indices of the subarray.

For example, for the input array [1, -2, 3, 5, -1, 2], the subarray [3, 5, -1, 2] gives the maximum sum. Your task is to implement an algorithm that reads the array from standard input and outputs the elements of the desired subarray to standard output.

inputFormat

The input is provided via standard input (stdin). The first line contains an integer (n) ((1 \le n \le 10^5)) that denotes the number of elements in the array. The second line contains (n) space-separated integers representing the array elements.

outputFormat

Output the contiguous subarray with the largest sum to standard output (stdout) with each element separated by a single space.## sample

6
1 -2 3 5 -1 2

3 5 -1 2