TopCoder

Thumb 1
羽瀨川小鷹
我是布丁

User's AC Ratio

100.0% (28/28)

Submission's AC Ratio

36.6% (37/101)

Description

  你和滷肉是非常要好的朋友,以至於連他的心情起伏都掌握的很清楚,甚至可以預測他未來幾天的心情指數

  不過這樣還是不夠被稱為知心的朋友,於是你想知道,在哪些連續的天數內,他可以有最好的心情

  要知道連續天數的心情指數,並不是全部加起來取平均這麼簡單,是有公式的!!

  但是你身為他的好朋友,你當然知道,那公式就是:連續天數的心情指數和*連續天數內最小的心情指數

  現在你有每天的心情指數,你想知道哪段連續的天數可以有達到最High

Input Format

本題有多筆測試資料,請以EOF作為結束。(測試資料不超過十組)

第一行為總天數n 。接著下一行有n個心情指數。

數字範圍: 1≦all≦100000。

Output Format

第一行數字輸出最High是多High。

接著下一行是區段的範圍,若還有多組解,則輸出起點最小的,再來輸出終點最小。

Sample Input

6
3 1 6 4 5 2
6
1 1 1 1 1 1

Sample Output

60
3 5
6
1 6

Hints

Problem Source

原TIOJ1368 / 快樂暑假營第二次練習比賽。
(Northeastern Europe 2005) Problem Setter:ggm

Subtasks

No. Testdata Range Score
1 0 25
2 1 25
3 2 25
4 3 25

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1500 65536 262144 1
1 1500 65536 262144 2
2 1500 65536 262144 3
3 1500 65536 262144 4