Liên minh huyền thoại là trò chơi rất được yêu thích. Nhưng, là học sinh Lê Quý Đôn, các bạn không nên thích liên minh huyền thoại, mà nên thích liên minh dãy ngoặc. Bài toán sau sẽ giúp các bạn có cái nhìn khác về liên minh dãy ngoặc. Các bạn có một xâu kí tự chỉ gồm các kí tự '?' , '(' hoặc ')'. Các bạn hãy tìm cách đổi tất cả kí tự '?' thành ')' hoặc '(' để liên minh dãy ngoặc của xâu kí tự sau khi đổi là lớn nhất.

Liên minh dãy ngoặc chính là tên gọi khác của dãy ngoặc con ở bài D. Liên minh dãy ngoặc của một xâu là một dãy ngoặc đúng, có thể nhận được bằng cách xoá đi một vài hoặc 0 kí tự của xâu S và giữ nguyên thứ tự của các kí tự còn lại. Dãy ngoặc đúng được định nghĩa đệ quy như sau : dãy ngoặc rỗng là dãy ngoặc đúng, nếu A, B là các dãy ngoặc đúng thì (A) và AB cũng là dãy ngoặc đúng.

Ví dụ: () là một liên minh dãy ngoặc của ())) 

           (()) là một liên minh dãy ngoặc của (()() vì có thể bỏ đi ký tự '(' ở vị trí 4 để nhận được (())

           () không là liên minh dãy ngoặc của ))((

Dữ liệu vào

Dòng đầu chứa một số nguyên dương n (n <= 170901).

Dòng tiếp theo là n kí tự liên tiếp chỉ gồm '?','(' hoặc ')'.

Dữ liệu ra

Một số nguyên dương là liên minh dãy ngoặc lớn nhất.