Description

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.

Input Format

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 Format

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.

4
4 1 2 3

(4+((1+2)+3))
19
3 6 10

Hint

Sample Explanation $1$

See the Background.

Constraints

For all testdata, $1 \le n \le 20$.

Translated by ChatGPT 5