무서운 아르바이트

성화는 편의점 사장이고, 임금 체계가 특이하다.

• 날마다 일의 양이 달라서 날짜별 일급이 미리 정해져 있다.
• 급여는 당일에 주지 않고 퇴직할 때 한꺼번에 준다.
• 성화는 욕심이 많아서 일한 기간 중 일급이 가장 낮은 날을 기준으로 계산한다. 즉 (일한 날수) 곱하기 (그 기간의 최저 일급)만큼만 준다.
• 일급이 날마다 다르다는 사실을 숨기려고, 한 번 퇴직한 사람은 다시 채용하지 않는다. 그래서 취직하면 일을 시작한 날부터 끝내는 날까지 하루도 빠질 수 없다.

준수는 월세를 내야 해서 이 편의점에 취직하려 한다. 퇴직자에게 급여 체계를 들었고, 앞으로 $n$일 동안의 일급도 모두 알아냈다. 준수는 1일부터 $n$일 사이에서 연속한 구간 하나를 골라 그 기간만 일한다. 오래 일할수록 급여가 커지는 것은 아니다.

준수가 받을 수 있는 최대 급여를 구하라.

첫째 줄에 일할 수 있는 날의 수 $n$이 주어진다. ($0 < n \le 100000$)

둘째 줄에 1일부터 $n$일까지의 일급 $T_i$가 순서대로 주어진다. ($0 < T_i \le 1000000$)

준수가 받을 수 있는 최대 급여를 한 줄에 출력한다.