Hide

Problem H
Higher Arithmetic

/problems/higherarithmetic/file/statement/en/img-0001.png

Captchas are getting more and more elaborate. It started with doing simple calculations like $7 + 2$, and now, it has evolved into having to distinguish chihuahuas from double chocolate chip muffins.

To combat the rise of smarter bots, the Internet Captcha Production Company (ICPC) has outdone itself this time: given a distorted image containing many integers, find the maximum value that can be expressed using each of the given integers exactly once, using addition, multiplication, and arbitrary parentheses.

After unsuccessfully trying to solve such a captcha for an hour straight, Katrijn is terribly frustrated. She decides to write a program that outputs a valid arithmetic expression with maximal value.

Input

The input consists of:

One line with an integer $n$ ($1 \le n \le 10^5$), the number of integers in the captcha.
One line with $n$ integers $a$ ($1 \le a \le 10^6$), the integers in the captcha.

Output

Output a valid arithmetic expression with maximal value, where each integer from the input list is used exactly once. The usual order of operations applies: within parentheses, multiplication takes priority over addition. The output expression may use at most $10^6$ characters, must not contain any spaces, and must conform to the grammar shown in Figure 1. Such an expression exists for any possible input.

If there are multiple valid solutions, you may output any one of them.

\begin{align*} \langle expression \rangle ::= ~ & \text{`\texttt{(}'}~ \langle expression \rangle ~ \text{`\texttt{)}'} \\ | ~ ~ ~ & \langle expression \rangle ~ \text{`\texttt{*}'}~ \langle expression \rangle \\ | ~ ~ ~ & \langle expression \rangle ~ \text{`\texttt{+}'}~ \langle expression \rangle \\ | ~ ~ ~ & \langle integer \rangle \\ \end{align*}

Figure 1: The grammar of a valid arithmetic expression. $\langle integer \rangle $ refers to an integer from the input list. Note that the expression must not contain any spaces.

Sample Input 1	Sample Output 1
4 1 2 3 4	3((1+2)4)

Sample Input 2	Sample Output 2
3 13 37 1	(1+13)*37

Sample Input 3	Sample Output 3
4 1 1 1 1	((1+1)*(1+1))

Problem HHigher Arithmetic

Input

Output

Problem H
Higher Arithmetic