Longest Subsequence Sum

You are given an array of n integers. Your task is to determine a contiguous subsequence of the array whose sum is maximum. In case there are multiple subsequences with the same maximum sum, you must choose the one with the shortest length. Note that the array indices are based on 1-indexing.

Details:

• If all numbers in the array are negative, the answer is the maximum element and its corresponding index should be used as both the start and end index.
• If a subsequence is found, output three values: the maximum sum, the starting index, and the ending index (all indices are 1-indexed).

Example: For the array [1, -3, 2, 1, -1], the best subsequence is [2, 1] with a sum of 3, starting at index 3 and ending at index 4.

inputFormat

The input is given via stdin as follows:

• The first line contains an integer \(n\) (\(1\leq n \leq 10^5\)), representing the number of elements in the array.
• The second line contains \(n\) space-separated integers, which are the elements of the array.

outputFormat

The output should be printed to stdout and consist of three space-separated integers: the maximum subsequence sum, the starting index, and the ending index. The indices must be reported using 1-indexing.## sample

5
1 -3 2 1 -1

3 3 4