수확

1 × N 크기의 긴 밭에 벼가 한 줄로 심어져 있다. 준희는 이 벼를 모두 수확하려고 한다. 가운데에 있는 벼를 수확하려면 밭을 헤집고 들어가야 하므로, 매 순간 양 끝에 있는 벼만 수확할 수 있다. 처음에는 첫 번째 벼 또는 N번째 벼를 수확할 수 있고, 첫 번째 벼를 수확했다면 그다음에는 두 번째 벼 또는 N번째 벼를 수확할 수 있으며, 이런 식으로 이어진다.

수확으로 얻는 이익은 다음과 같이 계산한다. 어떤 벼의 가치가 v이고 이 벼를 k번째로 수확한다면, 그 벼에서 v × k 만큼의 이익을 얻는다.

예를 들어 벼의 가치가 왼쪽부터 차례로 1, 3, 1, 5, 2일 때, 위치 1, 5, 2, 3, 4의 벼를 이 순서대로 수확하면 이익은 1×1 + 2×2 + 3×3 + 1×4 + 5×5 = 43이 되며, 이것이 이 밭에서 얻을 수 있는 최대 이익이다.

벼의 개수 N과 각 벼의 가치가 주어질 때, 모든 벼를 수확하여 얻을 수 있는 최대 이익을 구하는 프로그램을 작성하시오.

첫째 줄에 벼의 개수 N (1 ≤ N ≤ 2,000)이 주어진다. 이어지는 N개의 줄에는 각 벼의 가치 v (1 ≤ v ≤ 1,000)가 왼쪽부터 순서대로 한 줄에 하나씩 주어진다.

첫째 줄에 얻을 수 있는 최대 이익을 출력한다.