사전 검색 최적화

N개의 단어가 검색 빈도순으로 정렬되어 있다. 이 단어들을 이진 탐색 트리(BST)에 배치하여 총 검색 비용을 최소화하려고 한다.

각 단어 i의 검색 빈도는 F_i이다. 단어 i가 BST에서 깊이 d_i(루트의 깊이는 0)에 위치할 때, 해당 단어의 검색 비용은 (d_i + 1) * F_i이다.

총 검색 비용 = 모든 단어의 검색 비용의 합

최소 총 검색 비용을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (1 <= N <= 250)

둘째 줄에 N개의 정수가 공백으로 구분되어 주어진다. i번째 정수는 단어 i의 검색 빈도 F_i이다. (1 <= F_i <= 1,000,000)

출력

최소 총 검색 비용을 출력한다.

입출력 예시

입력 1

3
1 1 1

출력 1

5

입력 2

3
3 1 2

출력 2

10