Higher Arithmetic

시간 제한4초메모리 제한1024 MB

요약

양의 정수 n개가 주어질 때, 각 수를 정확히 한 번씩만 사용하고 덧셈, 곱셈, 괄호를 써서 만들 수 있는 가장 큰 값을 내는 수식을 출력한다.

난이도: 보통10점 중 6점
유형: 그리디, 정렬, 수학, 구현
정답자: 아직 제출이 없습니다

문제

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.

입력

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 a valid arithmetic expression with maximal value, where each integer from the input list is used exactly once. The usual order of operations applies. The output expression may use at most $10^6$ characters and must not contain any spaces. Such an expression exists for any possible input.

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

예제3

예제 1
입력
```
4
1 2 3 4
```
예상 출력
```
3*((1+2)*4)
```
예제 2
입력
```
3
13 37 1
```
예상 출력
```
(1+13)*37
```
예제 3
입력
```
4
1 1 1 1
```
예상 출력
```
((1+1)*(1+1))
```