Good days#4139
Bill is developing a new mathematical theory that describes human emotions. His latest research focuses on studying how good and bad days affect people's memories of different periods in their lives.
Recently, Bill devised a method to describe how good or bad a day was in a person's life by associating each day with a certain non-negative integer. Bill calls this number the emotional value of that day. The higher this number, the better the day. Bill believes that the significance of a certain period in a person's life equals the sum of the emotional values of each day in the period, multiplied by the minimum emotional value among the days in this period. This methodology reflects that a period which may be quite good on average can be spoiled by a single bad day.
Now Bill wants to analyze his own life and find the period with the maximum significance. Help him do this.
The first line contains the number of days (1 \leq n \leq 100\,000) in Bill's life that he wants to study. The next integers a_1,\, a_2,\, \ldots,\, a_n are the emotional values of the days. All numbers are within the range from to 10^6. The input numbers are separated by spaces and line breaks.
Print the maximum significance of a period in Bill's life on the first line. On the second line, print two numbers and (l \leq r) indicating that the period from day to day (inclusive) in Bill's life had the maximum possible significance.
Example 1