부분 수열의 점수

수열 $s = s_1, s_2, \dots, s_n$의 점수는 $\sum_{i=1}^{n} i \times s_i$로 구할 수 있다.

연속한 부분 수열도 그 자체로 하나의 수열이므로, 점수를 계산할 때 가중치 $1, 2, 3, \dots$은 부분 수열의 첫 항부터 다시 센다. 즉, 부분 수열 $s_l, s_{l+1}, \dots, s_r$의 점수는 $\sum_{i=l}^{r} (i - l + 1) \times s_i$이다.

수열 $s$의 연속한 부분 수열의 점수 중 최댓값을 구하는 프로그램을 작성하시오. 길이가 0인 부분 수열도 고를 수 있고, 그 점수는 0이다.

첫째 줄에 $n$ ($1 \le n \le 200\,000$)이 주어진다.

둘째 줄에 $s_1, s_2, \dots, s_n$이 주어진다. ($|s_i| \le 10^7$)

첫째 줄에 수열 $s$의 연속한 부분 수열의 점수 중 최댓값을 출력한다.