Maximum Subarray Problem

Given an array of integers, your task is to find the contiguous subarray (containing at least one number) with the largest sum. In other words, find indices \(i\) and \(j\) (with \(0 \leq i \leq j < n\)) such that the sum \(\sum_{k=i}^j a_k\) is maximized. This is a classic problem that can be solved efficiently using Kadane's algorithm.

If the input array is empty, output 0 and an empty subarray.

inputFormat

The input is given via stdin in the following format:

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

outputFormat

Output the answer to stdout in two lines. The first line should contain the maximum subarray sum. The second line should contain the contiguous subarray (its elements are space-separated) that yields this sum. If the subarray is empty, output an empty line for the second line.

## sample

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

6
4 -1 2 1

</p>