Background

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:

There are three intermediate sums $5, 5, 10$, and their total is: $5+5+10=20$.

Second way to add parentheses:

The intermediate sums are $3, 6, 10$, and their total is $19$.

Problem 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