1368 . Get High!!
TopCoder
Tags
Description
你和滷肉是非常要好的朋友，以至於連他的心情起伏都掌握的很清楚，甚至可以預測他未來幾天的心情指數
不過這樣還是不夠被稱為知心的朋友，於是你想知道，在哪些連續的天數內，他可以有最好的心情
要知道連續天數的心情指數，並不是全部加起來取平均這麼簡單，是有公式的!!
但是你身為他的好朋友，你當然知道，那公式就是：連續天數的心情指數和$\times$連續天數內最小的心情指數
現在你有每天的心情指數，你想知道哪段連續的天數可以有達到最High
Input Format
本題有多筆測試資料，請以EOF作為結束。(測試資料不超過十組)
第一行為總天數$n$ 。接著下一行有$n$個心情指數。
數字範圍： $0\le all\le 100000$。
Output Format
第一行數字輸出最High是多High。
接著下一行是區段的範圍，若還有多組解，則輸出起點最小的，如果有多組起點最小的解，輸出這些解裡終點最小者。
Sample Input 1
6
3 1 6 4 5 2
6
1 1 1 1 1 1
3 1 6 4 5 2
6
1 1 1 1 1 1
Sample Output 1
60
3 5
6
1 6
3 5
6
1 6
Hints
Problem Source
原TIOJ1368 / 快樂暑假營第二次練習比賽。
(Northeastern Europe 2005) Problem Setter：ggm
2024/06/29 Update: Added $\LaTeX$ by owoovo_shih
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 25 |
| 2 | 1 | 25 |
| 3 | 2 | 25 |
| 4 | 3 | 25 |