Go: package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

func main() {
	var n int
	fmt.Scan(&n)

	var sc = bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)

	ps := make([]int, n)
	for i := range ps {
		sc.Scan()
		p, _ := strconv.Atoi(sc.Text())
		ps[i] = p
	}

	mp := make([]int, n+1)
	ans := make([]byte, 0)
	var pp, max int
	for _, p := range ps {
		mp[p] = 1
		if p < pp {
			if mp[p+1] != 1 {
				fmt.Println(":(")
				return
			}
			ans = append(ans, ')')
		} else {
			for i := max; i < p-1; i++ {
				ans = append(ans, '(')
			}
			ans = append(ans, '(')
			ans = append(ans, ')')
		}
		if p > max {
			max = p
		}
		pp = p
	}
	fmt.Println(string(ans))
}

C++: // template version 1.14
using namespace std;
#include <bits/stdc++.h>

// varibable settings
#define int long long
const int INF=1e18;
const int MOD=1e9+7;

// define basic macro {{{
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define _rrep(i,n) rrepi(i,0,n)
#define rrepi(i,a,b) for(int i=(int)((b)-1);i>=(int)(a);--i)
#define rrep(...) _overload3(__VA_ARGS__,rrepi,_rrep,)(__VA_ARGS__)
#define each(i,a) for (auto&& i : a)
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define pb(a) push_back(a)
#define mp(a, b) make_pair(a, b)
#define mt(a, b, c) make_tuple(a, b, c)
#define ceil(a,b) ((a)+(b)-1)/(b)
#define is_in(x, a, b) ((a)<=(x) && (x)<(b))
#define uni(x) sort(all(x));x.erase(unique(all(x)),x.end())
#define ub upper_bound
#define lb lower_bound
#define posl(A, x) (lower_bound(all(A), x)-A.begin())
#define posu(A, x) (upper_bound(all(A),x)-A.begin())
template<class T> inline void chmax(T &a, const T &b) { if((a) < (b)) (a) = (b); }
template<class T> inline void chmin(T &a, const T &b) { if((a) > (b)) (a) = (b); }

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef long double ld;
typedef pair<int,int> pii;
typedef tuple<int,int,int> iii;

template<typename T> using PQ = priority_queue<T, vector<T>, greater<T>>;
struct Fast { Fast(){ std::cin.tie(0); ios::sync_with_stdio(false); } } fast;

#if defined(PCM) || defined(LOCAL)
  #include "lib/dump.hpp"
#else
  #define dump(...) 42
  #define dump_1d(...) 42
  #define dump_2d(...) 42
#endif
//}}}

signed main() {
  int n;cin>>n;
  vector<int> p(n);
  rep(i, n) {
    cin>>p[i];
  }
  dump(p);

  string ans = "";
  int k = 0;
  int m = 0;
  multiset<int> st;
  rep(i, 0, n+1) st.insert(i);
  rep(i, n){
    while (k<p[i]){
      ans+="(";
      m++;

      k = m;
    }
    if (k>p[i]){
      cout << ":(" << endl;
      return 0;
    }
    ans += ")";
    auto it = st.find(p[i]);
    it = st.erase(it);
    k = *(prev(it));
  }
  dump(ans);

  int lev = 0;
  rep(i, sz(ans)){
    if (ans[i]=='(') lev++;
    if (ans[i]==')') lev--;
    if (lev<0){
      cout << ":(" << endl;
      return 0;
    }
  }
  if (lev==0){
    cout << ans << endl;
  }
  else{
    assert(false);
    cout << ":(" << endl;
  }

  return 0;
}

C++: #include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<string>
#include<algorithm>
#include<vector> 
#include<limits>
#include<numeric>
#include<type_traits>
#include<math.h>
#include<fstream>
#include<set>
#include<queue>
#include<stack>
using namespace std;
typedef long long ll;

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define repi(i,a,b) for(int i = (int)(a); i < (int)(b); i++)
#define out(str) cout << str << endl
#define ALL(a) (a).begin(),(a).end()
#define INF (1<<29)

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

int now=0,N;

int main(){
    cin>>N;
    int A[N];
    rep(i,N){
        cin>>A[i];
        A[i]--;
    }
    stack<int> sta;
    string ans="";
    bool isok = true;
    rep(i,N){
        if(now<=A[i]){
            while(now<=A[i]){
                ans += "(";
                sta.push(now);
                now++;
            }
        }
        else if(sta.top() != A[i]){
            isok = false;
            break;
        }
        ans+=")";
        sta.pop();
    }
    if(isok)out(ans);
    else out(":(");
    
}

C++: #include <iostream>
#include <stack>
using namespace std;
string s = "";
int n, p;

main()
{
    cin >> n;
    int c = 1;
    stack<int> st;
    for (int i = 0; i < n; i++)
    {
        cin >> p;
        while (c <= p)
        {
            st.push(c);
            s += '(';
            c++;
        }
        if (!st.empty() && st.top() == p)
        {
            s += ')';
            st.pop();
        }
        else
        {
            cout << ":(" << endl;
            return 0;
        }
    }
    cout << s << endl;
}

C++: #include <iostream>
#include <string>
#include <utility>
#include <vector>
using namespace std;
int p[100010];
vector<int> v;
string s;
int main(){
	int i,n;
	cin >> n;
	for(i=0;i<n;i++){
		cin >> p[i];
	}
	v.push_back(1); s.push_back('(');
	int cnt = 2;
	for(i=0;i<n;i++){
		if(i!=0 && p[i] - p[i-1]==-1){
			v.pop_back();
			s.push_back(')');
		}else{
			while(1){
				int x = v.back();
				if(x<p[i]){
					v.push_back(cnt); cnt++;
					s.push_back('(');
				}else if(x==p[i]){
					v.pop_back(); s.push_back(')');
					break;
				}else{
					cout << ":(" << endl;
					return 0;
				}
			}
		}
	}
	cout << s << endl;
}

C++: #include <bits/stdc++.h>

using namespace std;

#define REP(i,n) for(ll (i) = (0);(i) < (n);++i)
#define REV(i,n) for(ll (i) = (n) - 1;(i) >= 0;--i)
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
#define SHOW1d(v,n) {REP(WW,n)cerr << v[WW] << ' ';cerr << endl << endl;}
#define SHOW2d(v,WW,HH) {REP(W_,WW){REP(H_,HH)cerr << v[W_][H_] << ' ';cerr << endl;}cerr << endl;}
#define ALL(v) v.begin(),v.end()
#define Decimal fixed<<setprecision(20)
#define INF 1000000000
#define LLINF 1000000000000000000LL
#define MOD 998244353
#define fastcin() cin.tie(0);ios::sync_with_stdio(false)

typedef long long ll;
typedef pair<ll,ll> P;

int main(){

	int n;cin >> n;
	vector<P> v(n);
	REP(i, n){
		cin >> v[i].FI;
		v[i].SE = i + 1;
	}

	sort(ALL(v),greater<P>());

	int now = n;
	stack<int> st;
	vector<char> ans;

	REP(i, n){
	//cout << "v " << v[i].FI << " " << v[i].SE << endl;
		while(now > 0 && now >= v[i].SE){
			ans.PB(')');
			st.push(now);
			now--;
		}
	//	cout << " " << now << " " << st.top() << endl;
		if(st.empty() || st.top() != v[i].SE){
			cout << ":(" << endl;
			return 0;
		}

		ans.PB('(');
		st.pop();
	}

	REP(i,ans.size())cout << ans[ans.size() - i - 1];
	cout << endl;


	return 0;
}