Maximum Beauty Subarray

You are given an array of ( n ) integers: ( a_1, a_2, \dots, a_n ). A subarray is a contiguous segment of the array. The beauty of a subarray is defined as the sum of its elements, i.e., for a subarray spanning from index ( l ) to ( r ), its beauty is ( \sum_{i=l}^{r} a_i ). Your task is to find the subarray with the maximum beauty. In case there are multiple subarrays with the same maximum beauty, select the shortest one. If a tie still exists, choose the one with the smallest starting index.

Formally, find integers ( l ) and ( r ) (1-based indexing) such that the sum ( S = \sum_{i=l}^{r} a_i ) is maximized. With tie-breaking rules:

• If there is more than one subarray with maximum sum, choose the one where \( r - l + 1 \) is minimized.
• If still tied, choose the one with the smallest \( l \).

inputFormat

The first line of input contains an integer ( n ) (the number of elements in the array). The second line contains ( n ) space-separated integers representing the array elements, where ( -10^9 \leq a_i \leq 10^9 ).

outputFormat

Output three space-separated integers on a single line: the maximum beauty (i.e., the maximum subarray sum), the starting index, and the ending index (both 1-based) of the optimal subarray.## sample

8
1 -2 3 10 -4 7 2 -5

18 3 7