시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 155 36 29 27.885%

문제

크기가 N(1≤N≤100,000)인 1차원 배열 A[1], …, A[N]이 있다. 어떤 i, j(1≤i≤j≤N)에 대한 점수는, (A[i]+…+A[j])×Min{A[i], …, A[j]}가 된다. 즉, i부터 j까지의 합에다가 i부터 j까지의 최소값을 곱한 것이 점수가 된다.

배열이 주어졌을 때, 최대의 점수를 갖는 부분배열을 골라내는 프로그램을 작성하시오.

입력

첫째 줄에 정수 N이 주어진다. 다음 줄에는 A[1], …, A[N]을 나타내는 정수들이 주어진다. 각각의 정수들은 음이 아닌 값을 가지며, 1,000,000을 넘지 않는다.

출력

첫째 줄에 최대 점수를 출력한고, 둘째 줄에 그 구간의 시작 위치(i)와 끝 위치(j)를 출력한다.

예제 입력 1

6
3 1 6 4 5 2

예제 출력 1

60
3 5

힌트

W3sicHJvYmxlbV9pZCI6IjE5ODkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJkODBcdWJkODRcdWJjMzBcdWM1ZjQgXHVhY2UwXHViOTc0XHVhZTMwIDIiLCJkZXNjcmlwdGlvbiI6IjxwPlx1ZDA2Y1x1YWUzMFx1YWMwMCBOKDEmbGU7TiZsZTsxMDAsMDAwKVx1Yzc3OCAxXHVjYzI4XHVjNmQwIFx1YmMzMFx1YzVmNCBBWzFdLCAmaGVsbGlwOywgQVtOXVx1Yzc3NCBcdWM3ODhcdWIyZTQuIFx1YzViNFx1YjVhNCBpLCBqKDEmbGU7aSZsZTtqJmxlO04pXHVjNWQwIFx1YjMwMFx1ZDU1YyBcdWM4MTBcdWMyMThcdWIyOTQsIChBW2ldKyZoZWxsaXA7K0Fbal0pJnRpbWVzO01pbntBW2ldLCAmaGVsbGlwOywgQVtqXX1cdWFjMDAgXHViNDFjXHViMmU0LiBcdWM5ODksIGlcdWJkODBcdWQxMzAgalx1YWU0Y1x1YzljMFx1Yzc1OCBcdWQ1NjlcdWM1ZDBcdWIyZTRcdWFjMDAgaVx1YmQ4MFx1ZDEzMCBqXHVhZTRjXHVjOWMwXHVjNzU4IFx1Y2Q1Y1x1YzE4Y1x1YWMxMlx1Yzc0NCBcdWFjZjFcdWQ1NWMgXHVhYzgzXHVjNzc0IFx1YzgxMFx1YzIxOFx1YWMwMCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmMzMFx1YzVmNFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWNkNWNcdWIzMDBcdWM3NTggXHVjODEwXHVjMjE4XHViOTdjIFx1YWMxNlx1YjI5NCBcdWJkODBcdWJkODRcdWJjMzBcdWM1ZjRcdWM3NDQgXHVhY2U4XHViNzdjXHViMGI0XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzgxNVx1YzIxOCBOXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViMmU0XHVjNzRjIFx1YzkwNFx1YzVkMFx1YjI5NCBBWzFdLCAmaGVsbGlwOywgQVtOXVx1Yzc0NCBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgXHVjODE1XHVjMjE4XHViNGU0XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxXHVhYzAxXHVjNzU4IFx1YzgxNVx1YzIxOFx1YjRlNFx1Yzc0MCBcdWM3NGNcdWM3NzQgXHVjNTQ0XHViMmNjIFx1YWMxMlx1Yzc0NCBcdWFjMDBcdWM5YzBcdWJhNzAsIDEsMDAwLDAwMFx1Yzc0NCBcdWIxMThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjZDVjXHViMzAwIFx1YzgxMFx1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWFjZTAsIFx1YjQ1OFx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVhZGY4IFx1YWQ2Y1x1YWMwNFx1Yzc1OCBcdWMyZGNcdWM3OTEgXHVjNzA0XHVjZTU4KGkpXHVjNjQwIFx1YjA1ZCBcdWM3MDRcdWNlNTgoailcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjE5ODkiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJGZWVsIEdvb2QiLCJkZXNjcmlwdGlvbiI6IjxwPkJpbGwgaXMgZGV2ZWxvcGluZyBhIG5ldyBtYXRoZW1hdGljYWwgdGhlb3J5IGZvciBodW1hbiBlbW90aW9ucy4gSGlzIHJlY2VudCBpbnZlc3RpZ2F0aW9ucyBhcmUgZGVkaWNhdGVkIHRvIHN0dWR5aW5nIGhvdyBnb29kIG9yIGJhZCBkYXlzIGluXHVmYjAydWVudCBwZW9wbGUmcnNxdW87cyBtZW1vcmllcyBhYm91dCBzb21lIHBlcmlvZCBvZiBsaWZlLjxcL3A+XHJcblxyXG48cD5BIG5ldyBpZGVhIEJpbGwgaGFzIHJlY2VudGx5IGRldmVsb3BlZCBhc3NpZ25zIGEgbm9uLW5lZ2F0aXZlIGludGVnZXIgdmFsdWUgdG8gZWFjaCBkYXkgb2YgaHVtYW4gbGlmZS4gQmlsbCBjYWxscyB0aGlzIHZhbHVlIHRoZSBlbW90aW9uYWwgdmFsdWUgb2YgdGhlIGRheS4gVGhlIGdyZWF0ZXIgdGhlIGVtb3Rpb25hbCB2YWx1ZSBpcywgdGhlIGJldHRlciB0aGUgZGF5IHdhcy4gQmlsbCBzdWdnZXN0cyB0aGF0IHRoZSB2YWx1ZSBvZiBzb21lIHBlcmlvZCBvZiBodW1hbiBsaWZlIGlzIHByb3BvcnRpb25hbCB0byB0aGUgc3VtIG9mIHRoZSBlbW90aW9uYWwgdmFsdWVzIG9mIHRoZSBkYXlzIGluIHRoZSBnaXZlbiBwZXJpb2QsIG11bHRpcGxpZWQgYnkgdGhlIHNtYWxsZXN0IGVtb3Rpb25hbCB2YWx1ZSBvZiB0aGUgZGF5IGluIGl0LiBUaGlzIHNjaGVtYSByZVx1ZmIwMmVjdHMgdGhhdCBnb29kIG9uIGF2ZXJhZ2UgcGVyaW9kIGNhbiBiZSBncmVhdGx5IHNwb2lsZWQgYnkgb25lIHZlcnkgYmFkIGRheS48XC9wPlxyXG5cclxuPHA+Tm93IEJpbGwgaXMgcGxhbm5pbmcgdG8gaW52ZXN0aWdhdGUgaGlzIG93biBsaWZlIGFuZCBmaW5kIHRoZSBwZXJpb2Qgb2YgaGlzIGxpZmUgdGhhdCBoYWQgdGhlIGdyZWF0ZXN0IHZhbHVlLiBIZWxwIGhpbSB0byBkbyBzby48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIHRoZSBpbnB1dCBmaWxlIGNvbnRhaW5zIG4gJm1kYXNoOyB0aGUgbnVtYmVyIG9mIGRheXMgb2YgQmlsbCZyc3F1bztzIGxpZmUgaGUgaXMgcGxhbm5pbmcgdG8gaW52ZXN0aWdhdGUgKDEgJmxlOyBuICZsZTsgMTAwIDAwMCkuIFRoZSByZXN0IG9mIHRoZSBmaWxlIGNvbnRhaW5zIG4gaW50ZWdlciBudW1iZXJzIGE8c3ViPjE8XC9zdWI+LCBhPHN1Yj4yPFwvc3ViPiwgLi4uLCBhPHN1Yj5uPFwvc3ViPiZuYnNwO3JhbmdpbmcgZnJvbSAwIHRvIDEwPHN1cD42PFwvc3VwPiZuYnNwOyZtZGFzaDsgdGhlIGVtb3Rpb25hbCB2YWx1ZXMgb2YgdGhlIGRheXMuIE51bWJlcnMgYXJlIHNlcGFyYXRlZCBieSBzcGFjZXMgYW5kXC9vciBsaW5lIGJyZWFrcy48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5PbiB0aGUgZmlyc3QgbGluZSBvZiB0aGUgb3V0cHV0IGZpbGUgcHJpbnQgdGhlIGdyZWF0ZXN0IHZhbHVlIG9mIHNvbWUgcGVyaW9kIG9mIEJpbGwmcnNxdW87cyBsaWZlLjxcL3A+XHJcblxyXG48cD5PbiB0aGUgc2Vjb25kIGxpbmUgcHJpbnQgdHdvIG51bWJlcnMgbCBhbmQgciBzdWNoIHRoYXQgdGhlIHBlcmlvZCBmcm9tIGwtdGggdG8gci10aCBkYXkgb2YgQmlsbCZyc3F1bztzIGxpZmUgKGluY2x1c2l2ZSkgaGFzIHRoZSBncmVhdGVzdCBwb3NzaWJsZSB2YWx1ZS4gSWYgdGhlcmUgYXJlIG11bHRpcGxlIHBlcmlvZHMgd2l0aCB0aGUgZ3JlYXRlc3QgcG9zc2libGUgdmFsdWUsIHRoZW4gcHJpbnQgYW55IG9uZSBvZiB0aGVtLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==