상담실 앞에 \(N\)명의 학생이 줄을 서 있다. 학생은 \(1\)번부터 \(N\)번까지 번호가 매겨져 있으며, \(i\)번 학생을 상담하는 데 걸리는 시간은 \(P_i\)분이다.

상담 선생님은 한 번에 한 명의 학생만 상담할 수 있다. 학생들이 줄을 서는 순서에 따라서, 각 학생이 상담을 마치는 데 필요한 시간의 합이 달라지게 된다.

예를 들어, 총 \(5\)명의 학생이 있고 \(P_1 = 3\), \(P_2 = 1\), \(P_3 = 4\), \(P_4 = 3\), \(P_5 = 2\)인 경우를 생각해보자.

\([1, 2, 3, 4, 5]\) 순서로 상담을 받는다면, \(1\)번 학생은 \(3\)분 만에 상담을 마칠 수 있다. \(2\)번 학생은 \(1\)번 학생의 상담이 끝날 때까지 기다려야 하므로 \(3 + 1 = 4\)분이 걸린다. \(3\)번 학생은 \(1\)번, \(2\)번 학생의 상담이 끝날 때까지 기다려야 하므로 \(3 + 1 + 4 = 8\)분이 필요하다. \(4\)번 학생은 \(3 + 1 + 4 + 3 = 11\)분, \(5\)번 학생은 \(3 + 1 + 4 + 3 + 2 = 13\)분이 걸린다.

이 경우 각 학생이 상담을 마치는 데 필요한 시간의 합은 \(3 + 4 + 8 + 11 + 13 = 39\)분이다.

상담 순서를 \([2, 5, 1, 4, 3]\)으로 정하면, 각 학생이 상담을 마치는 데 필요한 시간의 합은 \(1 + 3 + 6 + 9 + 13 = 32\)분이다.

학생의 수 \(N\)과 각 학생을 상담하는 데 걸리는 시간 \(P_i\)가 주어졌을 때, 각 학생이 상담을 마치는 데 필요한 시간의 합의 최솟값을 구하시오.

입력 설명

첫 번째 줄에 학생의 수 \(N\)이 주어진다.

두 번째 줄에 각 학생을 상담하는 데 걸리는 시간 \(P_1, P_2, \dots, P_N\)이 공백으로 구분되어 주어진다.

출력 설명

각 학생이 상담을 마치는 데 필요한 시간의 합의 최솟값을 출력한다.

제한

\(1 \le N \le 1000\)

\(1 \le P_i \le 1000\)

예시 입력

5
3 1 4 3 2

예시 출력

32