Có $2n$ phần tử được chia thành $n$ cặp.

Với mỗi cặp, bạn phải gán dấu ngoặc mở cho cả hai phần tử, hoặc dấu ngoặc đóng cho cả hai phần tử. Bạn cần tạo ra một dãy ngoặc đúng từ dãy kết quả hoặc xác định rằng điều đó là không thể. Nếu có nhiều lời giải khả thi, hãy tìm lời giải có chuỗi ký tự nhỏ nhất theo thứ tự từ điển (trong số $2n$ dấu ngoặc, '(' nhỏ hơn ')').

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên $n$ ($1 \le n \le 200\,000$).

Dòng tiếp theo chứa $2n$ số nguyên $p_1, p_2, \dots, p_{2n}$ ($1 \le p_i \le n$). Tất cả các số nguyên từ $1$ đến $n$ đều xuất hiện đúng hai lần trong dãy này.

Dữ liệu ra

Nếu không thể chọn loại dấu ngoặc cho mỗi cặp để tạo thành một dãy ngoặc đúng, hãy in ra ( (biểu tượng mặt buồn kiểu Nga). Nếu không, hãy in ra dãy ngoặc đúng nhỏ nhất theo thứ tự từ điển.

Ví dụ

Dữ liệu vào 1

2
1 2 1 2

Dữ liệu ra 1

()()

Dữ liệu vào 2

1
1 1

Dữ liệu ra 2

(

Dữ liệu vào 3

4
4 3 1 2 3 2 1 4

Dữ liệu ra 3

(

Dữ liệu vào 4

4
3 1 2 1 4 3 2 4

Dữ liệu ra 4

(()()())

Dữ liệu vào 5

4
2 4 3 1 3 4 2 1

Dữ liệu ra 5

()()()()

Dữ liệu vào 6

4
4 4 3 3 1 2 1 2

Dữ liệu ra 6

(((())))

Dữ liệu vào 7

4
1 3 1 2 4 4 2 3

Dữ liệu ra 7

()(())()