Bracket Sequence

Time limit: 0.3s Memory limit: 128MB Input: Output:

Baby Bob is learning about mathematical expressions. He despises operands and operators, and only likes round brackets.

He's got a sequence AA of positive integers A1,A2,,ANA_1, A_2, \dots, A_N. He wants to bracketize the sequence. A bracketized sequence created from AA is a sequence of strings B1,B2,,BNB_1, B_2, \dots, B_N such that each BiB_i has length AiA_i, and BiB_i consists only of either opening brackets (, or closing brackets ), but not both.

For example let A=(1,3,4)A=(1,3,4).

  • A possible bracketized sequence created from AA is ), ))), ((((.
  • The sequence ), )(), (((( is not a bracketized sequence created from AA, because the second element consists of both opening and closing brackets.
  • The sequence (, )))), (((( is not a bracketized sequence created from AA, because the length of the second element is not 33.
  • The sequence (, ) is not a bracketized sequence created from AA, because it consists of only 22 strings.

Take the string B1+B2++BNB_1 + B_2 + \dots + B_N (i.e., concatenate the elements of the bracketized sequence). Bob wonders whether he can bracketize AA so that the resulting string is a valid bracket sequence. A bracket sequence is valid if 1 and + characters can be inserted into it so that it becomes a valid mathematical expression. For example, (((()))) is a valid bracket sequence if A=(1,3,4)A=(1,3,4).

Task

Write a program that finds such a bracket sequence or determines that it's impossible!

Input data

The first line contains the only integer NN. The second line contains NN integers AiA_i.

Output data

You need to print a valid bracket sequence created from AA or -1 if it's not possible to create one.

If there are multiple correct bracket sequences, output any.

Constraints and clarifications

  • 1N5001 \leq N \leq 500
  • 1Ai1 \leq A_i for each i=0N1i=0 \ldots N-1
  • A1+A2++AN50 000A_1 + A_2 + \ldots + A_N \leq 50 \ 000
# Points Constraints
1 0 Examples
2 20 N2N \leq 2
3 30 N20N \leq 20 and A1+A2++AN200A_1 + A_2 + \dots + A_N \leq 200
4 50 No additional constraints

Example 1

stdin

3
1 3 4

stdout

(((())))

Explanation

This sample case is explained in the statement.

Example 2

stdin

4
2 2 1 1

stdout

(())()

Explanation

In this sample the bracketized sequence is ((, )), (, ).

Example 3

stdin

2
2 1

stdout

-1

Log in or sign up to be able to send submissions!