불소 아주머니

Björn과 다른 사람 $n-1$명이 불소 아주머니를 만나기 위해 줄을 서 있다. 불소 아주머니를 만나는 것을 얼마나 무서워하는지는 사람마다 다르다. 사람들은 $1$부터 $n$까지 번호가 매겨져 있으며, 사람 $i$은 줄의 $i$번째 자리에 서 있다. 사람 $i$에게는 불소 아주머니를 얼마나 만나기 싫어하는지를 나타내는 값 $a_i$도 있다. 사람 $i$이 줄에서 자신의 자리에 대해 느끼는 기쁨은 $i \cdot a_i$이다. 일부 사람은 $a_i$가 음수일 수 있는데, 이는 실제로는 불소 아주머니를 만나고 싶어 하므로 기다려야 하는 것을 슬퍼한다는 뜻이다.

Björn은 불소 아주머니를 만나는 것에 완전히 무관심한 유일한 사람이다. 즉, $a_i = 0$인 유일한 사람이다. 게다가 그는 마음씨가 매우 착해서 줄에서 나갔다가 다시 줄의 어떤 자리에 들어가, 줄에 선 모든 사람의 기쁨의 합을 최대화하기로 한다. 모든 사람의 값 $a_i$이 주어질 때, Björn이 최적의 자리에 선 경우 줄에서 느끼는 기쁨의 합의 최댓값을 계산하는 프로그램을 작성하라.

채점

여러 테스트 케이스 그룹으로 해답을 테스트한다. 한 그룹의 점수를 얻으려면 그 그룹의 모든 테스트 케이스를 통과해야 한다.

그룹 | 점수 | 제한

$1$    |$32$|  $1 \leq n \leq 1000$

$2$    |$12$|  수열 $a_1 \dots a_n$은 비감소한다.

$3$    |$11$|  수열 $a_1 \dots a_n$은 비증가한다.

$4$    |$45$|  추가 제한 없음.

첫째 줄에 줄에 선 사람의 수를 나타내는 정수 $n$ ($1 \le n \le 10^6$)이 주어진다. 다음 줄에는 정수 $n$개가 주어지며, 그중 $i$번째 수 $-1000 \le a_i \le 1000$는 줄에 선 $i$번째 사람의 기쁨을 나타낸다.

줄에서 느끼는 기쁨의 합의 최댓값을 정수 하나로 출력한다.

Björn은 줄의 맨 끝에 선다. 이때 기쁨의 합은 $1 \cdot 1 + 2\cdot(-2) + 3 \cdot 0 = -3$이 된다.

Björn이 그 대신 줄의 맨 앞에 섰다면 기쁨의 합은 $1 \cdot 0 + 2 \cdot 1 + 3 \cdot (-2) = -4$이 되었을 것이고, 가운데에 섰다면 $1 \cdot 1 + 2 \cdot 0 + 3 \cdot (-2) = -5$이 되었을 것이다. 이 두 선택지는 모두 더 나쁘다.