Xét dãy ngoặc ~T~ có độ dài ~m~, gọi ~f_i~ là số dấu ngoặc mở "dư" của dãy tạo bởi ~i~ phần tử đầu tiên của ~T~. Cụ thể:

• ~f_0 = 0~.
• Nếu ~T_i = '('~ thì ~f_i = f_{i-1} + 1~, ngược lại ~f_i = f_{i-1} - 1~ với mọi ~1 \leq i \leq m~.

~T~ là dãy ngoặc đúng khi thỏa mãn cả hai điều kiện:

• ~min(f_0, f_1, f_2, ..., f_m) = 0~: số lượng dấu ngoặc mở "dư" không được âm tại bất kì tiền tố nào của ~T~.
• ~f_m = 0~: cả dãy ngoặc không dư dấu ngoặc mở nào.

Nhận xét: nếu thêm một dấu ngoặc mở vào đầu dãy (giả sử dấu ngoặc này có chỉ số là ~-1~ và không ảnh hưởng gì đến các chỉ số của các dấu ngoặc khác) thì tất cả phần tử của mảng ~f~ sẽ tăng lên ~1~.

Một cách chèn các dấu ngoặc để ~T~ trở thành dãy ngoặc đúng như sau:

• Đặt ~x = -min(f_0, f_1, f_2, ..., f_m)~ (~x \geq 0~).

• Thêm ~x~ dấu ngoặc mở vào đầu dãy, lúc này ~f_m = f_m + x~.

• Thêm ~f_m~ dấu ngoặc đóng

Code mẫu

/*#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")*/

#include <bits/stdc++.h>

#define for1(i,a,b) for (int i = a; i <= b; i++)
#define for2(i,a,b) for (int i = a; i >= b; i--)
#define int long long

#define sz(a) (int)a.size()
#define pii pair<int,int>
#define pb push_back

/*
__builtin_popcountll(x) : Number of 1-bit
__builtin_ctzll(x) : Number of trailing 0
*/

const long double PI = 3.1415926535897932384626433832795;
const int INF = 1000000000000000000;
const int MOD = 1000000007;
const int MOD2 = 1000000009;
const long double EPS = 1e-6;

using namespace std;

int n, res1, res2;
string s;

signed main() {

    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    // freopen("cf.inp", "r", stdin);
    // freopen("cf.out", "w", stdout);

    cin >> n >> s;
    for (auto f : s) {
        if (f == '(') res2++;
        else res2--;

        if (res2 == -1) {
            res1++;
            res2++;
        }
    }

    for1(i,1,res1) cout << '(';
    cout << s;
    for1(i,1,res2) cout << ')';

}