행복한 소

민호는 아끼는 소 한 마리를 키운다. 소가 행복하면 민호도 행복하기에, 민호는 전 재산을 털어 가장 맛있는 여물 $N$개를 샀다.

민호는 여물을 관리하기 쉽도록 폭이 좁고 길이가 아주 긴 창고에 순서대로 넣었고, 왼쪽부터 1번, 2번, 3번, ..., $N$번 여물이라고 부르기로 했다. 여물마다 소가 먹었을 때 느끼는 행복이 다를 수 있다. 예를 들어 1번 여물을 먹으면 소가 느끼는 행복은 20이지만, 2번 여물을 먹으면 10일 수 있다. 이 값을 여물의 행복도라고 하자.

여물은 날이 지날수록 숙성되어 맛이 좋아진다. 행복도가 $H$인 여물을 $d$일째에 먹이면 소가 느끼는 행복은 $H \times d$이다. 여물을 산 당일이 1일째이고 그 다음 날이 2일째다.

백만 년 숙성시킨 여물을 먹이면 소가 극락을 맛보겠지만 민호는 그때까지 기다릴 수 없다. 그래서 여물을 산 날부터 $N$일째까지 하루에 한 개씩 소에게 먹이기로 했다. 창고의 폭이 좁아서 가운데에 있는 여물은 꺼낼 수 없고, 왼쪽 끝이나 오른쪽 끝에서 하나만 꺼낼 수 있다. 즉 $i$번부터 $j$번까지 ($1 \le i \le j \le N$) 여물이 남아 있다면 민호는 $i$번 여물이나 $j$번 여물 중 하나를 골라 먹여야 한다. $i$번과 $j$번이 아닌 여물은 먹일 수 없다.

민호는 소가 최대한 행복하기를 바란다. $N$일에 걸쳐 여물을 모두 먹였을 때 소가 느끼는 행복의 합이 최대가 되는 값을 구하자.

첫째 줄에 여물의 개수 $N$ ($1 \le N \le 2000$)이 주어진다.

둘째 줄에 여물의 행복도 $H_1, H_2, \dots, H_N$ ($1 \le H_i \le 1000$)이 공백을 사이에 두고 $N$개 주어진다.

$N$일에 걸쳐 여물을 모두 먹였을 때 소가 느끼는 행복의 합 중 최댓값을 출력한다.