\(\color{red}{\text{Spoiler Alert}_{{}_{{}^{{}^{v2.0}}}}}\)

\(\color{red}{\text{Khuyến khích bạn đọc trước khi đọc phần lời giải xin hãy thử code ra thuật của mình dù nó có sai hay đúng}}\)

\(\color{red}{\text{Sau đó từ phần bài giải và thuật toán trước đó mà đối chiếu, rút nhận xét với thuật của mình và thu được bài học (không lãng phí thời gian đâu).}}\)

\(\color{orange}{\text{Hint 1 <Brute-forces>}}\)

• Thử tạo từng xâu dãy ngoặc

Với mỗi xâu mình kiểm tra xem nó có tạo ra được dãy \(p\) hay không

Từ đó cập nhật kết quả

Đầu tiên ta tìm các cặp đối xứng và sắp xếp theo thứ tự xuất hiện của \(")"\)

Sau đó ta sẽ đếm số lượng \(")"\) trên từng đoạn đối xứng và vứt vảo dãy \(w\)

Cuối cùng thì xuất dãy \(w\) hoặc in ra \(-1\) nếu không tồn tại dãy như thế

\(\color{goldenrod}{\text{Approach <Brute-force>}}\)

• Hàm \(main()\) sẽ thử nhận, xử lí và xuất kết quả

Đầu tiên sẽ nhận các phần tử mảng \(p\)

Sau đó sẽ thực hiện \(build()\) các dãy

Rồi mình sẽ xuất \(-1\) nếu không tồn tại dãy thỏa mãn hoặc xuất dãy \(w\) ra nếu tìm được

\(_{_{\color{purple}{\text{Complexity : }} O(2^{2 \times n} \times n ^ 2)\ \color{purple}{\text{auxiliary time}}\ ||\ O(n)\ \color{purple}{\text{auxiliary memory}}}}\)

C++

int main()
{
    /// Nhan mang p
    n = readInt();
    p.resize(n);
    for (int &x : p) cin >> x;

    /// Xu li
    build();

    /// Xuat ket qua
    if (invalid) /// neu khong tim thay
    {
        cout << -1;
        return 0;
    }
    for (int x : w) cout << x << ' '; /// neu tim thay
    return 0;
}

• Hàm \(build()\) để xây xâu \(s\) gồm \("("\) và \(")"\)

Xâu gồm \(n\) kí tự \("("\) và \(")"\) nên khi \(|s| = 2 * n\) ta sẽ kiểm tra và cập nhật

Ngược lại, từ một xâu \(s\) mình sẽ thử điền từng kí tự \("("\) hoặc \(")"\) vào bên phải cùng của \(s\)

\(_{_{\color{purple}{\text{Complexity : }} O(2 ^ {2 \times n} \times n ^ 2)\ \color{purple}{\text{auxiliary time}}\ ||\ O(n)\ \color{purple}{\text{auxiliary memory}}}}\)

C++

void build(string s = "") {
    if (s.size() == 2 * n) /// Da build xong xau s
    {
        if (check(s)) update(s); /// Neu kiem tra xau s thoa man thi cap nhat day w
        return ;
    }

    build(s + '('); /// thu xay them dau ngoac mo
    build(s + ')'); /// thu xay them dau ngoac dong
}

• Hàm \(check()\) để kiểm tra nếu từ xâu \(s\) ta mã hóa được ra xâu \(p\)

Duyệt qua từng phần tử, nếu phần tử hiện tại là \(")"\) thì đếm số lượng phía trước

Đưa số lượng đếm được vào mảng mã hóa \(p\) hiện tại, kiểm tra xem \(p\) hiện tại có bằng \(p\) yêu cầu không

\(_{_{\color{purple}{\text{Complexity : }} O(n ^ 2)\ \color{purple}{\text{auxiliary time}}\ ||\ O(n)\ \color{purple}{\text{auxiliary memory}}}}\)

C++

bool check(string s) { /// kiem tra xau s co ma hoa ra day p hay khong
    vector<int> current_p; /// mang ma hoa p hien tai
    for (int cur = 0; cur < s.size(); ++cur)
    {
        if (s[cur] == ')') /// neu ki tu hien tai la ")"
        {
            int cnt = 0;
            for (int pre = 0; pre < cur; ++pre)
            {
                if (s[pre] == '(') /// dem so luong phan tu "("
                {
                    cnt++;
                }
            }
            current_p.push_back(cnt); /// them phan tu do vao mang p hien tai
        }
    }
    return current_p == p; /// neu mang p hien tai la mang p ma hoa duoc thi return true
}

• Hàm \(update()\) để mã hóa từ xâu \(s\) ra xâu \(w\)

Đánh dấu lại là tồn tại dãy \(w\) thỏa mãn

Mình sẽ tìm các cặp tương ứng \("("\) và \(")"\) bằng ở phần \(getPairs()\)

Sau đó mình sắp xếp các dãy ở phần \(bubbleSort()\)

Cuối cùng mình sẽ mã hóa sang xâu \(w\) ở phần \(encode()\)

\(_{_{\color{purple}{\text{Complexity : }} O(n ^ 2)\ \color{purple}{\text{auxiliary time}}\ ||\ O(n)\ \color{purple}{\text{auxiliary memory}}}}\)

C++

void update(string s) { /// cap nhat lai day w
    invalid = false; /// danh dau da tim thay

    vector<pair<int, int> > suit; /// mang cac cap tuong ung
    getPairs(suit, s); /// tim cac cap tuong ung
    bubbleSort(suit);  /// sap xep cac cap tuong ung
    encode(suit, s);   /// ma hoa cac cap tuong ung
}

• Hàm \(getPairs()\) để tìm các cặp tương ứng \("("\) và \(")"\)

Gọi mảng \(pos\) là vị trí của từng kí tự trong xâu

Mỗi lần mình duyệt qua xâu, nếu tìm thấy một cặp \("()"\)

Mình xóa 2 kí tự khỏi xâu \(s\)

Thêm một cặp tương ứng là vị trí của 2 kí tự đó vào mảng \(suit\)

Mình cập nhật vị trí của cả mảng \(pos\) từ vị trí bị xóa dồn cả phần sau lên 2 ô

Giờ gán lại \(pos.size = s.size\) cho nó hợp lí

Sau đó mình cho con trỏ chạy lại từ đầu

\(_{_{\color{purple}{\text{Complexity : }} O(n ^ 2)\ \color{purple}{\text{auxiliary time}}\ ||\ O(n)\ \color{purple}{\text{auxiliary memory}}}}\)

C++

void getPairs(vector<pair<int, int> > &suit, string s) { /// lay tung cap "(" va ")" tuong ung
    int n = s.size();
    vector<int> pos(n); /// Vi tri cua no trong xau ban dau
    for (int i = 0; i < n; ++i)
        pos[i] = i + 1; /// Khoi tao vi tri dau tien

    for (int i = 0; i + 1 < n; ++i)
    {
        if (s[i] == '(' && s[i + 1] == ')') /// Neu tim thay mot cap tuong ung
        {
            suit.push_back(make_pair(pos[i], pos[i + 1])); /// them cap do vao mang
            s.erase(i, 2); /// xoa phan tu di

            for (int j = i; j + 2 < n; ++j) /// don mang len 2 don vi
                pos[j] = pos[j + 2];

            pos.resize(s.size());

            i = -1; /// duyet lai tu dau
            // cout << s << endl; /// debug
        }
    }
}

• Hàm \(bubbleSort()\) mình sẽ sắp xếp cả mảng \(getPairs()\) theo \(")"\) tăng dần

Duyệt qua từng cặp phần tử, nếu một cặp lớn hơn cặp kia thì đổi vị trí hai cặp

\(_{_{\color{purple}{\text{Complexity : }} O(n ^ 2)\ \color{purple}{\text{auxiliary time}}\ ||\ O(1)\ \color{purple}{\text{auxiliary memory}}}}\)

C++

void bubbleSort(vector<pair<int, int> > &suit) { /// sap xep theo ")" tang dan
    int len = suit.size();
    for (int i = 0; i + 1 < len; ++i)
        for (int j = i + 1; j < len; ++j)
            if (suit[i].second > suit[j].second) /// neu 2 cap khong dung vi tri thi dao lai
                swap(suit[i], suit[j]);
}

• Hàm \(encode()\) để mã hóa sang xâu \(w\)

Làm mới mảng \(w\)

Duyệt từng cặp \(barrack\) và đếm xem có bao nhiêu phần tử \(")"\) thì vứt vào dãy \(w\)

\(_{_{\color{purple}{\text{Complexity : }} O(n ^ 2)\ \color{purple}{\text{auxiliary time}}\ ||\ O(n)\ \color{purple}{\text{auxiliary memory}}}}\)

void encode(vector<pair<int, int> > suit, string s) { /// ma hoa sang day w
    w.clear();
    for (pair<int, int> barrack : suit) { /// voi moi cap tuong ung
        // cout << barrack.first << ' ' << barrack.second << endl;

        int cnt = 0;
        for (int i = barrack.first; i <= barrack.second; ++i) /// duyet qua doan nay
        {
            if (s[i] == ')') /// dem xem co bao nhieu phan tu ")"
            {
                cnt++;
            }
        }
        w.push_back(cnt); /// dua vao mang w
    }
}

\(\color{green}{\text{Preference TLE Code }}\): Approach

\(^{^{\color{purple}{\text{Complexity : }} O(2 ^ {2 \times n} \times n ^ 2)\ \color{purple}{\text{time}}\ ||\ O(n)\ \color{purple}{\text{memory}}}}\)

int n;
vector<int> p, w;
bool invalid = true;

/// O(n ^ 2) time - O(n) space
void getPairs(vector<pair<int, int> > &suit, string s) { /// lay tung cap "(" va ")" tuong ung
    int n = s.size();
    vector<int> pos(n); /// Vi tri cua no trong xau ban dau
    for (int i = 0; i < n; ++i)
        pos[i] = i + 1; /// Khoi tao vi tri dau tien

    for (int i = 0; i + 1 < n; ++i)
    {
        if (s[i] == '(' && s[i + 1] == ')') /// Neu tim thay mot cap tuong ung
        {
            suit.push_back(make_pair(pos[i], pos[i + 1])); /// them cap do vao mang
            s.erase(i, 2); /// xoa phan tu di

            for (int j = i; j + 2 < n; ++j) /// don mang len 2 don vi
                pos[j] = pos[j + 2];

            pos.resize(s.size());

            i = -1; /// duyet lai tu dau
            // cout << s << endl; /// debug
        }
    }
}

/// O(n ^ 2) time - O(1) space
void bubbleSort(vector<pair<int, int> > &suit) { /// sap xep theo ")" tang dan
    int len = suit.size();
    for (int i = 0; i + 1 < len; ++i)
        for (int j = i + 1; j < len; ++j)
            if (suit[i].second > suit[j].second) /// neu 2 cap khong dung vi tri thi dao lai
                swap(suit[i], suit[j]);
}

/// O(n ^ 2) time - O(n) space
void encode(vector<pair<int, int> > suit, string s) { /// ma hoa sang day w
    w.clear();
    for (pair<int, int> barrack : suit) { /// voi moi cap tuong ung
        // cout << barrack.first << ' ' << barrack.second << endl;

        int cnt = 0;
        for (int i = barrack.first; i <= barrack.second; ++i) /// duyet qua doan nay
        {
            if (s[i] == ')') /// dem xem co bao nhieu phan tu ")"
            {
                cnt++;
            }
        }
        w.push_back(cnt); /// dua vao mang w
    }
}

/// O(n ^ 2) time - O(n) space
void update(string s) { /// cap nhat lai day w
    invalid = false; /// danh dau da tim thay

    vector<pair<int, int> > suit; /// mang cac cap tuong ung
    getPairs(suit, s); /// tim cac cap tuong ung
    bubbleSort(suit);  /// sap xep cac cap tuong ung
    encode(suit, s);   /// ma hoa cac cap tuong ung
}

/// O(n ^ 2) time - O(n) space
bool check(string s) { /// kiem tra xau s co ma hoa ra day p hay khong
    vector<int> current_p; /// mang ma hoa p hien tai
    for (int cur = 0; cur < s.size(); ++cur)
    {
        if (s[cur] == ')') /// neu ki tu hien tai la ")"
        {
            int cnt = 0;
            for (int pre = 0; pre < cur; ++pre)
            {
                if (s[pre] == '(') /// dem so luong phan tu "("
                {
                    cnt++;
                }
            }
            current_p.push_back(cnt); /// them phan tu do vao mang p hien tai
        }
    }
    return current_p == p; /// neu mang p hien tai la mang p ma hoa duoc thi return true
}

/// O(2 ^ (2 * n) * n ^ 2) time - O(n) space
void build(string s = "") {
    if (s.size() == 2 * n) /// Da build xong xau s
    {
        if (check(s)) update(s); /// Neu kiem tra xau s thoa man thi cap nhat day w
        return ;
    }

    build(s + '('); /// thu xay them dau ngoac mo
    build(s + ')'); /// thu xay them dau ngoac dong
}

/// O(2 ^ (2 * n) * n ^ 2) time - O(n) space
int main()
{
    /// Nhan mang p
    n = readInt();
    p.resize(n);
    for (int &x : p) cin >> x;

    /// Xu li
    build();

    /// Xuat ket qua
    if (invalid) /// neu khong tim thay
    {
        cout << -1;
        return 0;
    }
    for (int x : w) cout << x << ' '; /// neu tim thay
    return 0;
}

\(\color{orange}{\text{Hint 2 <Branch-and-bound>}}\)

• Chúng ta sẽ cải thiện thuật toán bằng cách loại bỏ các trường hợp không cần thiết

• Nhận xét rằng xâu ta cần xử lí là một dãy ngoặc đúng, vì thế ta không cần tạo các dãy vô nghĩa

• Nhận xét rằng dùng biến global, reference kiểu mảng thì tốt hơn là phải clone mảng và thêm phần tử rồi xử lí tiếp mảng đó

• Nhận xét rằng trong phần kiểm tra ta có thể dùng kết quả trước để tính tiếp phần sau

• Nhận xét rằng việc tìm các cặp tương ứng có thể đổi sang thuật toán khác để không cần tạo thêm mảng

• Nhận xét rằng việc sắp xếp có thể cải thiện bằng thuật toán tốt hơn và đặc biệt độ dài \(s \leq 2 \times n\)

• Nhận xét rằng việc mã hóa sang xâu \(w\) có thể được cải thiện bằng quy hoạch động tổng tiền tố

• Nhận xét rằng chỉ cần một dãy \(w\) tim được là xuất ra luôn, khi này ta dừng ngay chương trình lại

\(\color{goldenrod}{\text{Approach <Branch-and-bound>}}\)

• Hàm \(build()\) ta gọi \(diff\) là độ chênh lệch giữa số lượng \("("\) và \(")"\)

Nếu \((diff \geq 2 \times n - |s|)\), khi ta thêm \("("\) thì sau đó khi \(|s| = n\) số lượng \("("\) sẽ lớn áp đảo \(")"\) hay \(diff > 0\)

Nếu \((diff \leq 0)\), khi ta thêm \(")"\) thì nó sẽ không có cặp tương ứng

\(_{_{\color{purple}{\text{Complexity : }} O(catalan(n) \times n ^ 2)\ \color{purple}{\text{auxiliary time}}\ ||\ O(1)\ \color{purple}{\text{auxiliary memory}}}}\)

C++

/// O(catalan(n) * n ^ 2) time - O(1) space
void build(int diff = 0) {
    if (s.size() == 2 * n) /// Da build xong
    {
        if (check()) update();
        return ;
    }

    if (diff < 2 * n - s.size()) /// Neu them '(' thi cuoi cung diff > 0
    {
        s += '(';        /// <- them o day
        build(diff + 1); /// <- xu li o day
        s.pop_back();    /// <- nho xoa o day
    }

    if (diff > 0) /// Neu them ')' thi khong co ton tai '(' tuong ung
    {
        s += ')';        /// <- them o day
        build(diff - 1); /// <- xu li o day
        s.pop_back();    /// <- nho xoa o day
    }
}

• Hàm \(check()\) ta cải tiến như sau

Gọi \(last\) là vị trí cuối cùng đã xét

Gọi \(val\) là giá trị đếm được tính tới hiện tại

Gọi \(index\) là vị trí của giá trị \(p\)

Gọi \(cur\) là vị trí hiện tại mình đang xét

Khi gặp giá trị \(")"\)

Ta chỉ cần cập nhật tiếp từ vị trí \(last\) tăng giá trị \(val\)

Nếu \(val \neq p[index]\) thì \(s\) không thể mã hóa ra xâu \(p\)

Duyệt tới vị trí \(index + 1\) tiếp theo và gán \(last\) là giá trị hiện tại

\(_{_{\color{purple}{\text{Complexity : }} O(n)\ \color{purple}{\text{auxiliary time}}\ ||\ O(1)\ \color{purple}{\text{auxiliary memory}}}}\)

C++

bool check() {
    int last = 0, val = 1, index = 0;
    for (int cur = 0; cur < s.size(); ++cur)
    {
        if (s[cur] == ')')
        {
            for (int pre = last + 1; pre < cur; ++pre) /// Tiep tuc dem '('
                if (s[pre] == '(')
                    val++; /// Gia tri dem duoc hien tai

            if (val != p[index++]) return false; /// Khong the ma hoa ra xau p
            last = cur; /// Cap nhat vi tri cuoi
        }
    }

    return true;
}

• Hàm \(getPairs()\) ta cải tiến như sau

Gọi \(pre\) là vị trí trái đang xét

Gọi \(cur\) là vị trí phải đang xét

Độ dài xâu \(s\) là \(2 \times n\) nên mình chỉ cần duyệt \(n\) lần lấy cặp

Nếu \(s[pre] + s[cur] = "()"\)

Ta sẽ gán \(s[pre] = s[cur] = useless\) với giá trị vô nghĩa \(useless \neq "("\) và \(useless \neq ")"\)

Ta thêm cặp \((pre, cur)\) vào mảng \(suit\)

Đưa con trỏ \(pre\) sang trái tới khi giá trị hiện tại không còn vô nghĩa

Đưa con trỏ \(cur\) sang phải tới khi giá trị hiện tại không còn vô nghĩa

Còn trong trường hợp còn lại ta đưa \(pre, cur\) là sang phải tới khi gặp phần tử không vô nghĩa \(\Rightarrow (pre, cur) \rightarrow (cur, nxt)\)

\(_{_{\color{purple}{\text{Complexity : }} O(n)\ \color{purple}{\text{auxiliary time}}\ ||\ O(1)\ \color{purple}{\text{auxiliary memory}}}}\)

C++

void getPairs(vector<pair<int, int> > &suit) {
    int pre = 0, cur = 1;
    while (suit.size() < n) /// co n cap tat ca
    {
        if (s[pre] == '(' && s[cur] == ')') {
            s[pre] = s[cur] = '|'; /// gan gia tri vo nghia
            suit.push_back(make_pair(pre + 1, cur + 1)); /// tim duoc cap tuong ung
            while (s[pre] == '|') pre--; /// dua con tro sang trai
            while (s[cur] == '|') cur++; /// dua con tro sang phai
        }
        else {
            int nxt = cur + 1;
            while (s[nxt] == '|') nxt++; /// tim vi tri tiep theo
            tie(pre, cur) = make_tuple(cur, nxt); /// (pre, cur) = (cur, nxt)
        }
    }
}

• Hàm \(countSort()\) ta làm như sau

Vì mỗi phần tử vị trí \(")"\) phân biệt, ta sẽ lưu giá trị tại vị trí \(")"\) là vị trí \("("\)

Duyệt qua từng giá trị tại các vị trí tăng dần, ta sẽ thêm vào mảng \(suit\) một cặp vị trí (\("("\) và \(")"\)) mới tăng dần

\(_{_{\color{purple}{\text{Complexity : }} O(n)\ \color{purple}{\text{auxiliary time}}\ ||\ O(n)\ \color{purple}{\text{auxiliary memory}}}}\)

C++

void countSort(vector<pair<int, int> > &suit) {
    vector<int> leftval(2 * n + 1, 0);
    for (int i = 0; i < n; ++i)
        leftval[suit[i].second] = suit[i].first; /// luu vi tri '(' vao vi tri cua ')'

    suit.clear(); /// xoa mang
    for (int right = 1; right < leftval.size(); ++right) /// duyet tung vi tri ')' tang dan
        if (leftval[right] != 0)
            suit.push_back(make_pair(leftval[right], right)); /// them cap vi tri tuong ung ('(', ')') tang dan
}

• Hàm \(encode()\) ta làm như sau

Gọi \(f[n]\) là số lượng \(")"\) trong đoạn \([1, n]\)

Với \(f[0] = 0\) ta tính được \(f[l..r] = f[r] - f[l - 1]\)

Gọi \(last\) là vị trí cuối cùng xét được

Khi mã hóa thêm một cặp \((left, right)\) mới

Ta cập nhật đoạn \(f[last + 1..right - 1] = f[last]\)

Và ta có vị trí \(f[right] = f[last] + 1\)

Ta thêm giá trị \(f[right] - f[left - 1]\) vào dãy \(w\)

Cập nhật giá trị \(last\)

\(_{_{\color{purple}{\text{Complexity : }} O(n)\ \color{purple}{\text{auxiliary time}}\ ||\ O(1)\ \color{purple}{\text{auxiliary memory}}}}\)

void encode(vector<pair<int, int> > suit) {
    vi f(2 * n + 2, 0); /// f[n] = so luong ')' trong doan [1..n]
    int last = 0;
    for (int cur = 0; cur < n; ++cur) {
        int left  = suit[cur].first;
        int right = suit[cur].second;
        for (int j = last + 1; j < right; ++j) /// doan nay chua co them phan tu ')'
            f[j] = f[last];

        f[right] = f[right - 1] + 1; /// them ohan tu ')' vao
        w.push_back(f[right] - f[left - 1]); /// ma hoa duoc mot phan tu vao day w
        last = right; /// cap nhat gia tri cuoi
    }

    for (int x : w) cout << x << ' ';
    exit(0);
}

\(\color{green}{\text{Preference TLE Code }}\): Branch-and-bound

\(^{^{\color{purple}{\text{Complexity : }} O(catalan(n) \times n ^ 2)\ \color{purple}{\text{time}}\ ||\ O(n)\ \color{purple}{\text{memory}}}}\)

int n;
vector<int> p, w;
string s;

/// O(n ^ 2) time - O(1) space
void getPairs(vector<pair<int, int> > &suit) {
    int pre = 0, cur = 1;
    while (suit.size() < n) /// co n cap tat ca
    {
        if (s[pre] == '(' && s[cur] == ')') {
            s[pre] = s[cur] = '|'; /// gan gia tri vo nghia
            suit.push_back(make_pair(pre + 1, cur + 1)); /// tim duoc cap tuong ung
            while (s[pre] == '|') pre--; /// dua con tro sang trai
            while (s[cur] == '|') cur++; /// dua con tro sang phai
        }
        else {
            int nxt = cur + 1;
            while (s[nxt] == '|') nxt++; /// tim vi tri tiep theo
            tie(pre, cur) = make_tuple(cur, nxt); /// (pre, cur) = (cur, nxt)
        }
    }
}

/// O(n) time - O(1) space
void encode(vector<pair<int, int> > suit) {
    vi f(2 * n + 2, 0); /// f[n] = so luong ')' trong doan [1..n]
    int last = 0;
    for (int cur = 0; cur < n; ++cur) {
        int left  = suit[cur].first;
        int right = suit[cur].second;
        for (int j = last + 1; j < right; ++j) /// doan nay chua co them phan tu ')'
            f[j] = f[last];

        f[right] = f[right - 1] + 1; /// them ohan tu ')' vao
        w.push_back(f[right] - f[left - 1]); /// ma hoa duoc mot phan tu vao day w
        last = right; /// cap nhat gia tri cuoi
    }

    for (int x : w) cout << x << ' ';
    exit(0);
}

/// O(n) time - O(n) space
void countSort(vector<pair<int, int> > &suit) {
    vector<int> leftval(2 * n + 1, 0);
    for (int i = 0; i < n; ++i)
        leftval[suit[i].second] = suit[i].first; /// luu vi tri '(' vao vi tri cua ')'

    suit.clear(); /// xoa mang
    for (int right = 1; right < leftval.size(); ++right) /// duyet tung vi tri ')' tang dan
        if (leftval[right] != 0)
            suit.push_back(make_pair(leftval[right], right)); /// them cap vi tri tuong ung ('(', ')') tang dan
}

/// O(n ^ 2) time - O(1) space
void update() {
    vector<pair<int, int> > suit;
    getPairs(suit);
    countSort(suit);
    encode(suit);
}

/// O(n) time - O(1) space
bool check() {
    int last = 0, val = 1, index = 0;
    for (int cur = 0; cur < s.size(); ++cur)
    {
        if (s[cur] == ')')
        {
            for (int pre = last + 1; pre < cur; ++pre) /// Tiep tuc dem '('
                if (s[pre] == '(')
                    val++; /// Gia tri dem duoc hien tai

            if (val != p[index++]) return false; /// Khong the ma hoa ra xau p
            last = cur; /// Cap nhat vi tri cuoi
        }
    }

    return true;
}

/// O(catalan(n) * n ^ 2) time - O(1) space
void build(int diff = 0) {
    if (s.size() == 2 * n) /// Da build xong
    {
        if (check()) update();
        return ;
    }

    if (diff < 2 * n - s.size()) /// Neu them '(' thi cuoi cung diff > 0
    {
        s += '(';        /// <- them o day
        build(diff + 1); /// <- xu li o day
        s.pop_back();    /// <- nho xoa o day
    }

    if (diff > 0) /// Neu them ')' thi khong co ton tai '(' tuong ung
    {
        s += ')';        /// <- them o day
        build(diff - 1); /// <- xu li o day
        s.pop_back();    /// <- nho xoa o day
    }
}

/// O(catalan(n) * n ^ 2) time - O(n) space
int main()
{
    n = readInt();
    p.resize(n);
    for (int &x : p) cin >> x;

    build();
    cout << -1;
    return 0;
}