Informatica Online Judge

  암산 교실 (Large) [1924 / 0784]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 2   Total Tried : 2


The Champion of this Problem (C++) : gs16020 - 25ms / 4783byte
My Best Submission (C++) : N/A

[koistudy.net (34th 김진영)]
Writer ID : [gs16020]

Background

경곽 유치원의 인기스타인 쭈너니는 평소 뽐내는 것을 좋아한다.

어느 날 쭈너니는 자신의 멋진 수학실력을 뽐내기 위해 주어진 숫자들을 곱하거나 더해서 만들 수 있는 최대의 수를 암산으로 푸는 놀라운 모습을 보여준다.

그런데 쭈너니를 지켜보던 규민이는 주어진 숫자가 모두 2 이상의 양수임을 깨닫고 전부 곱하기만 하면 된다는 사실을 깨닫는다.

쭈너니의 단순한 트릭이 괘씸해진 규민이는 쭈너니에게 뺄셈을 한번 무조건 사용해서 만들 수 있는 최대의 수를 구해보라고 한다.

쭈너니는 대단히 당황했지만 자신의 이미지를 지켜야 하기 때문에 규민이의 요구를 거절할 수가 없었다.

불쌍한 쭈너니가 자신의 이미지를 지키도록 돕는 코드를 작성해보자.

Input

첫째 줄에는 주어지는 숫자의 개수 n이 주어진다.

둘째 줄에는 n개의 숫자들 ai(1<=i<=n)가 공백을 두고 주어진다.

[입력값의 정의역]
2 <= n <= 1,000,000
2 <= ai <= 10,000

Output

n개의 숫자의 순서를 바꾸지 않고 괄호와 *,+,- 연산을 하여 만들 수 있는 최대의 숫자를 출력하자. 단, -는 무조건 한번만 사용해야 한다.

수가 커질 수 있으니 1,000,000,007로 나눈 나머지를 출력하라.

단, 답이 음수면 음수 그대로 출력한다. (즉, 절댓값의 나머지에 -를 붙여서 출력하면 된다.)

IO Example

입력
5
4 7 5 3 2

출력
418

해설
4*7*5*3-2 인 경우가 최대이다.

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]