무거운 돌

Garsia-Wachs 알고리즘을 배운 뒤 다음 문제를 떠올렸다.

한 줄에 돌 무더기가 $n$개 놓여 있다. $i$번째 무더기에는 돌이 $a_i$개 있다. 모든 돌을 하나의 무더기로 합치려 한다.

먼저 $k$번째 무더기를 고른다. 선택한 무더기에 대해 다음 연산을 수행한다. 선택한 무더기의 왼쪽 또는 오른쪽에 인접한 무더기를 골라 두 무더기를 하나로 합친다. 합쳐진 새 무더기가 연산 후의 선택된 무더기가 된다. 이 연산을 $n-1$번 수행하면 무더기는 하나만 남는다. 합치기 한 번의 비용은 새 무더기에 있는 돌의 개수이다.

처음에 $k$번째 무더기를 골랐을 때 총 비용의 최솟값을 구하라. $k=1, 2, \ldots, n$에 대해 답을 출력하라.

첫째 줄에 정수 $n$이 주어진다 ($1 \le n \le 2 \cdot 10^5$).

둘째 줄에 정수 $a_1, a_2, \ldots, a_n$이 주어진다 ($1 \le a_i \le 10^6$).

정수 $n$개를 출력한다. $k$번째 수는 처음에 $k$번째 무더기를 골랐을 때의 총 비용의 최솟값이다.

처음에 4번째 무더기를 고르면 과정은 다음과 같이 진행될 수 있다.

{2, 1, 3, 5, 4} → {2, 1, 8, 4} → {2, 9, 4} → {11, 4} → {15}

총 비용은 8 + 9 + 11 + 15 = 43이다.