Maximum Subarray Sum

You are given an array of integers. Your task is to find the maximum sum of any contiguous subarray, and also return the 1-indexed starting and ending positions of that subarray.

If there are multiple subarrays with the same maximum sum, choose the subarray with the shortest length. The input begins with an integer n representing the number of elements, followed by n space-separated integers.

The formula for the subarray sum can be expressed as: \( \text{max_sum} = \max_{1 \leq i \leq j \leq n} \sum_{k=i}^{j} a_k \).

inputFormat

The first line contains a single integer n (1 ≤ n ≤ 10⁵), indicating the number of elements in the array. The second line contains n space-separated integers, each representing an element of the array.

outputFormat

Output three space-separated integers on a single line: the maximum subarray sum, the 1-indexed starting position, and the 1-indexed ending position of the subarray.

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

6 4 7