Good days
Bill is developing a new mathematical theory that explores how human emotions are influenced by good and bad days. His latest research focuses on understanding how these days impact people's memories of different life periods.
Bill has devised a method to evaluate how good or bad a day was by assigning it a non-negative integer, which he calls the emotional significance of that day. The higher this number, the better the day. According to Bill, the significance of a specific period in a person's life is calculated by summing the emotional significances of each day in that period and then multiplying by the minimum emotional significance of the days in that period. This approach captures the idea that even a generally good period can be negatively affected by a single bad day.
Bill now wants to analyze his own life to identify the period with the maximum significance. Your task is to help him find this period.
Input
The first line contains the number of days n (1 ≤ n ≤ 100000) that Bill wants to study. The subsequent lines contain n integers a[1], a[2], ..., a[n], each ranging from 0 to 10^6. These integers represent the emotional significances of the days and are separated by spaces and line breaks.
Output
On the first line, print the maximum significance of any period in Bill's life. On the second line, print two numbers l and r (l ≤ r), indicating that the period from the l-th to the r-th day (inclusive) in Bill's life has the maximum possible significance.