Time Limit: 1s
Memory Limit: 128MB
onacloud는 컴퓨터 프로그래밍 수업의 교수님이다. 그가 수업 진행용으로 선택한 교재는 총 N개 (1 ≤ N ≤ 2,000)의 챕터로 구성되어 있다. 이 교재는 특이하게도 진도를 앞장부터 뿐만 아니라 중간에 뒷장부터 진도가 나가도 상관없다. (즉, 수업 때 나갈 진도는 남은 챕터들 중 번호가 가장 작은 챕터, 또는 가장 큰 챕터 둘 중 하나를 정해서 진도를 나간다.) 이 교재로는 1장 2장 진도를 나가다가 뜬금없이 N장, N-1장, N-2장 수업을 진행하고 다시 3장, 다음엔 N-4장, N-5장 수업을 진행하는 식으로 진도를 나가도 학생들을 이해시키는데에 (아마도) 무리가 없다고 한다.
이 교재는 각 챕터마다 하나씩 과제가 있으며 과제마다 난이도가 존재한다. 뭐, 모든 과제가 그렇지만... 교재가 표기한 난이도와 학생들이 느끼는 과제의 체감난이도는 다르다. 그 이유는 학기가 진행될수록 피로(와 귀차니즘)이 누적되서 과제를 하려는 의지가 사라져가기 때문이다.
그렇기 때문에 학생들이 느끼는 과제의 체감난이도는, 과제의 순서에 비례해서 증가한다. 예를들어 5번째 과제로 난이도 3짜리 과제가 나왔다면, 학생들이 느끼는 체감 난이도는 5*3=15 이다.
onacloud 교수는 굉장한 가학성애자이기 때문에 어려운 과제일수록 학기 후반에 출제하여 학생들을 괴롭히고 싶어한다. 하지만 애석하게도(?) 과제는 수업 진도에 맞춰서 출제해야하기 때문에 체감난이도를 높이는게 쉽지가 않다. 예를 들어 오늘 1장과 29장을 나갔는데 뜬금없이 7장에 해당하는 과제를 낼 수는 없지 않은가...
이런 상황에서, 각 챕터별로 과제의 난이도가 주어졌을 때, 모든 진도를 끝마치고 나서 학생들이 느꼈을 체감난이도의 합을 최대로 하고싶다. 교수님을 도와 학생들을 괴롭혀보자. 어? 근데 나도 학생 아닌가? 음...조금 적당히 도와주자.
첫째 줄에 챕터의 개수 N이 주어진다. 다음에 N개의 줄에 걸쳐 각 챕터별 과제의 난이도 vi(1 ≤ vi ≤ 1,000) 주어진다.
과제의 체감난이도의 합의 최대값을 출력하자.
5 1 3 1 5 2
43
예제의 경우, 진도를 1장 -> 5장 -> 2장 -> 3장 -> 4장 순으로 나갔을 때 체감난이도가 1*1 + 2*2 + 3*3 + 4*1 + 5*5 = 43으로 최대가 된다. 진도는 순서대로 나가야하므로 1장 -> 3장 -> 5장 ->2장 ->4장 순으로 과제를 낼 수 없음에 유의하자.