P2308 Add Parentheses

Given a sequence of positive integers $a_1, a_2, \cdots, a_n$. Without changing the position of each element in the sequence, add them together by inserting parentheses. Record the sum obtained at each addition step with parentheses; we call it an intermediate sum. For example: Given the sequence $4, 1, 2, 3$. First way to add parentheses: $$ ((4+1)+(2+3))=((5)+(5))=(10) $$ There are three intermediate sums $5, 5, 10$, and their total is: $5+5+10=20$. Second way to add parentheses: $$ (4+((1+2)+3))=(4+((3)+3))=(4+(6))=(10) $$ The intermediate sums are $3, 6, 10$, and their total is $19$.

Now we add $n-1$ pairs of parentheses. The additions are performed according to the parentheses order, producing $n-1$ intermediate sums. Find the way to add parentheses that minimizes the total of the intermediate sums.

Two lines. The first line contains an integer $n$. The second line contains $n$ positive integers $a_1, a_2, \cdots, a_n$, each not exceeding $100$.

Output 3 lines. The first line is the parenthesization. The second line is the final total of the intermediate sums. The third line contains the $n-1$ intermediate sums, output from inner to outer and from left to right.

**Sample Explanation $1$** See the Background. **Constraints** For all testdata, $1 \le n \le 20$. Translated by ChatGPT 5