페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#8273
스페셜 저지

구간의 점수 1s 1024MB

문제

길이 N의 수열 A_1, A_2,\ \cdots,A_N이 있다.

해당 수열에서 어떤 구간 [s,e] (1 \le s \le e \le N)의 합을 최솟값으로 곱한 값을 점수라고 정의한다. 즉, (A_s + A_{s+1} + \cdots + A_{e-1} + A_e)\times min(A_s , A_{s+1} , \cdots , A_{e-1} , A_e)이 점수다.

가장 높은 점수와 그 구간을 구하는 프로그램을 작성하시오.


입력

첫 줄에 정수 N이 주어진다. (1\le N \le 100,000)

두 번째 줄에 N개의 정수 A_1, A_2,\ \cdots,A_N이 주어진다. (0 \le A_i \le 1,000,000)


출력

첫 줄에 최대 점수를 출력한다.

그 다음 줄에 해당 구간의 시작 위치와 끝 위치를 출력한다.


예제 

6
3 1 6 4 5 2
60
3 5


출처

NEERC 2005
로그인해야 코드를 작성할 수 있어요.