FJ는 많은 우유로 돈을 얻는 소에게 $N$개 $(1 \le N \le 2000)$ 맛있는 간식을 샀습니다. 하루 하나 팔아 기간 수입을 최대화합니다.

흥미로운 특징입니다:

• $1..N$ 번호로 순서대로 한 줄로 양끝 열린 긴 상자에 넣습니다. 매일 어느 끝에서든 하나 꺼냅니다.
• 좋은 와인, 맛있는 치즈처럼 오래될수록 좋아지고 비쌉니다.
• 균일하지 않아 더 좋고 본래 가치가 큰 것도 있습니다. 간식 $i$는 $v(i)$ 가치($1 \le v(i) \le 1000$)입니다.
• 오래된 것에 더 지불합니다. 나이 $a$에 $v(i)*a$를 냅니다.

상자 번호 $i$ 순서의 가치 $v(i)$가 주어질 때 최적 판매 순서의 최대 수입은?

첫 판매는 1일, 나이 $a=1$, 이후 하루마다 1 증가합니다.

입력

• 1번 줄: 한 정수 $N$.
• $2..N+1$번 줄: $i+1$번 줄 가치 $v(i)$.

출력

• 1번 줄: 최대 판매 수입.

예제

입력 1

5
1
3
1
5
2

출력 1

43

참고

가치 $1, 3, 1, 5, 2$를 번호 $1, 5, 2, 3, 4$ 순서로 팔아 $1*1 + 2*2 + 3*3 + 4*1 + 5*5 = 43$를 얻습니다.

출제: Marco Gallotta (2005).