You are given a permutation ~p~ of ~1, \dots, n~. Now you need to construct a valid bracket sequence of length ~n~ such that the following holds: if we create an undirected graph ~G~ with ~n~ vertices numbered ~1, \dots, n~, and add an edge from ~i~ to ~p_i~ if and only if the ~i~-th (with index starting from 1) character of the bracket sequence is a (, the resulting graph satisfies the condition that all vertices have degree ~1~.

It is guaranteed that for all ~i~ in the permutation, ~i \neq p_i~. Furthermore, all test cases are guaranteed to have a valid bracket sequence satisfying the above constraint.

Here are the formal definitions of "permutation" and "valid bracket sequence".

• Permutation: A sequence ~p~ of length ~n~ is a permutation of ~1, \dots, n~ if and only if for each ~i = 1, \dots, n~, ~i~ appears exactly once in ~p~.
• Valid bracket sequence: A valid bracket sequence can be defined using the three rules: (1) an empty sequence is a valid bracket sequence; (2) if A is a valid bracket sequence, then (A) is a valid bracket sequence; (3) if A and B are both valid bracket sequences, then AB is a valid bracket sequence.

An example of a valid bracket sequence is (())(), and an example of an invalid bracket sequence is ()) since the last ) does not have a matching (.

Input Specification

The first line of the input is an integer ~n~ ~(2 \leq n \leq 100, n \text{ is even})~ denoting the length of the permutation.

In the following line, there are ~n~ positive integers, separated by single spaces, denoting the permutation ~p~.

Output Specification

Output a line with a valid bracket sequence of length ~n~ denoting a solution satisfying the above constraints.

If there are multiple solutions, you may output any.

Note: the sample output is just a reference solution. The solution might be not unique.

Sample Input

4
2 3 4 1

Sample Output

()()

Explanation

Notice there are two left brackets at position ~1~ and ~3~. So we will add edge ~(1,2)~ and edge ~(3,4)~ to the graph. All vertices now have degree ~1~.

Constraints

For all test cases, ~p~ is a permuation of ~1, \dots, n~.

• Subtask 1 (30 points): ~n \leq 10~.
• Subtask 2 (30 points): ~n \leq 40~. Depends on subtask 1.
• Subtask 3 (40 points): ~n \leq 100~. Depends on subtask 1 and 2.

Update: For those experiencing presentation errors: it is likely that your output contains invalid characters, or you don't have output at all.