소들을 위한 간식

FJ는 젖을 많이 내는 젖소들에게 줄 맛있는 간식 $N$개($1 \le N \le 2000$)를 구입했다. FJ는 하루에 간식을 하나씩 팔며, 주어진 기간 동안 받는 돈을 최대로 하려고 한다.

이 간식에는 다음과 같은 특징이 있다.

• 간식에는 1번부터 $N$번까지 번호가 매겨져 있으며, 양쪽 끝이 뚫린 긴 상자 안에 한 줄로 놓여 있다. 어느 날이든 FJ는 간식 더미의 양 끝 중 어느 쪽에서든 간식 하나를 꺼낼 수 있다.
• 좋은 와인이나 맛있는 치즈처럼 간식도 오래될수록 좋아져서 더 높은 가격을 받는다.
• 간식마다 품질이 다르며, 본래 가치가 더 높은 간식도 있다. 간식 $i$의 가치는 $v(i)$($1 \le v(i) \le 1000$)이다.
• 젖소들은 오래 숙성된 간식에 더 많은 돈을 낸다. 나이가 $a$인 간식에는 젖소가 $v(i) \times a$를 낸다.

첫 번째 간식은 1일차에 팔리며 나이는 $a=1$이다. 그 다음 날부터는 하루가 지날 때마다 나이가 1씩 늘어난다.

상자 안에서 번호 순서대로 놓인 간식들의 가치 $v(i)$가 주어질 때, FJ가 판매 순서를 최적으로 정하면 얻을 수 있는 최대 금액은 얼마인가?

첫 줄에 정수 $N$이 주어진다. 둘째 줄부터 $N+1$번째 줄까지, $i+1$번째 줄에는 간식 $i$의 가치 $v(i)$가 주어진다.

FJ가 얻을 수 있는 최대 금액을 한 줄에 출력한다.