Page not loading? Try clicking here.
Placeholder

#8273
Special judge

구간의 점수 1s 1024MB

Problems

길이 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)이 점수다.

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


Input

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

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


Output

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

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


Example 

6
3 1 6 4 5 2
60
3 5


Source

NEERC 2005
You must sign in to write code.