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++: #include <bits/stdc++.h>
#define r(i,n) for(int i=0;i<n;i++)
#define int long long
using namespace std;
typedef pair<int,int>P;
typedef pair<P,int>P2;
#define fi first
#define se second


void END(){
  cout<<":("<<endl;
  exit(0);
}

signed main(){
  int n;
  cin>>n;
  int a[n];
  vector<P>ve;
  r(i,n){
    cin>>a[i];
    ve.push_back(P(a[i],i+1));
  }

  sort(ve.begin(),ve.end());

  r(i,n){
    a[i]=ve[i].second;
  }

  stack<P>st1;
  stack<P>st2;

  int del=1;

  string s;

  r(i,n){

    s+="(";

    ///st1.push(P(a[i],i+1));
    st2.push(P(a[i],i+1));

    while(!st2.empty()){
      if(st2.top().first!=del)break;
      s+=")";
      st2.pop();
      del++;
    }

    //cout<<st1.size()<<' '<<st2.size()<<endl;
  }

  if(!st1.empty()) END();
  if(!st2.empty()) END();

  cout<<s<<endl;

}


/*
typedef unsigned long long ull;


struct RollingHash{
  typedef unsigned long long ull;
  string S;
  ull B;
  int len;
  vector<ull> hash,p;
  RollingHash(){}
  RollingHash(string S_,ull B_=1000000007LL):
    S(S_),B(B_),len(S.length()),hash(len+1),p(len+1){
    hash[0]=0;p[0]=1;
    for(int i=0;i<len;i++){
      hash[i+1]=hash[i]*B+S[i];
      p[i+1]=p[i]*B;
    }
  }
  //S[l,r)
  ull find(int l,int r){
    return hash[r]-hash[l]*p[r-l];
  }
};

signed main(){
  int n;
  cin>>n;
  string s;
  cin>>s;
  string t=s;

  RollingHash S(s);
  RollingHash T(t);

  for(int i=1;i<n;i++){

    int idx=0 , F=0 ;
    ull A=S.find(0,i);

    for(int j=0;;j++){
      if(j%2==0){
        if(S.find(idx+i) != A){
          F++;
          break;
        }
      }
      else{

      }

      idx+=i-1;
    }

    if(!F){

    }
  }

}

*/

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

#define int long long

#define rep(i,n) for(int i=0;i<(n);i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;

template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

signed main(){
    int N;cin>>N;
    vint P(N);rep(i,N)cin>>P[i];

    int num=0;
    string ans;
    stack<int>s;

    rep(i,N){
        while(num<P[i]){
            num++;s.push(num);ans+="(";
        }
        if(s.empty()||s.top()!=P[i]){
            cout<<":("<<endl;
            return 0;
        }
        ans+=")";s.pop();
    }
    cout<<ans<<endl;
    return 0;
}

C++: #include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main(){
	int n;
	cin >> n;
	vector<int> p(n);
	for(int i=0; i<n; i++){
		cin >> p[i];
	}
	vector<int> st(1, 0);
	int curr = 0;
	string ans = "";
	for(int i=0; i<n; i++){
		if(p[i] < st.back()){
			ans = ":(";
			break;
		}
		while(curr < p[i]){
			curr++;
			ans += "(";
			st.push_back(curr);
		}
		st.pop_back();
		ans += ")";
	}
	cout << ans << endl;
	return 0;
}

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

int n;

string solve(const vector<int>& P){
  int cnt = 0;
  string ans;
  stack< pair<char, int > > st;

  for(const auto& p: P){
    while(cnt <= p){
      int ni;
     //  if(st.empty()){
     //    ni = 0;
     //  }else{
     //    ni = st.top().second + 1;
     //  }
      st.push( make_pair('(', cnt));
      cnt++;
      ans += '(';
    }
    if(st.top().second == p){
      st.pop();
      ans += ')';
    }else{
      return ":(";
    }
  }
  return ans;
}

int main(void){
  cin >> n;
  vector<int> p(n);
  for(auto& _p: p){
    cin >> _p;
    _p--;
  }

  cout << solve(p) << endl;
}

C++: #include<map>
#include<iostream>
#include<deque>
#include<algorithm>
#include<string>
#include<cctype>
#include<iomanip>
#include<vector>
#include<queue>
#include<tuple>
#include<stdio.h>
 
using namespace std;
#define REP(i,b,e) for(ll i=(ll)b;i<(ll)e;i++)
#define rep0(i,n) REP(i,0ll,n)
#define rep1(i,n) REP(i,1ll,n+1)
 
#define shosu setprecision(10)
 
typedef long long ll;
typedef pair<ll,ll> P;
typedef pair<P,ll> Q;
ll longinf=1ll<<60;
int inf=1<<29;
//mleしなければぜんぶllでかく。

int main(){
      cin.tie(0);
      ios::sync_with_stdio(false);
      /*rep0(i,8){
            rep0(j,8) cout<<board[i][j]<<" ";
            cout<<endl;
      }*/
      deque<int> deq;
      int n;
      cin>>n;
      int p[n];
      rep0(i,n){
            cin>>p[i];
      }
      int pos=0;
      string ans;
      int ok=true;
      rep0(i,n){
            if(pos<p[i]){
                  int addd=p[i]-pos;
                  rep1(j,addd){
                        ans+='(';
                  }
                  for(int k=pos+1;k<=p[i];k++){
                        deq.push_back(k);
                  }
                  ans+=')';
                  deq.pop_back();
                  pos=p[i];
            }
            else{
                  int b=deq.back();
                  if(b!=p[i]) ok=false;
                  ans+=')';
                  deq.pop_back();
            }
      }
      //cout<<ans<<endl;
      if(ok){
            cout<<ans<<endl;
      }
      else{
            cout<<":("<<endl;
      }

      return 0;
}

C++: #define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;
signed main() {
  ios::sync_with_stdio(false); cin.tie(0);
  int n;
  cin >> n;
  vector<int> in(n);
  for (int i = 0; i < n; i++) {
    cin >> in[i];
  }
  string res;
  int open = 0;
  for (int i = 0; i < n; i++) {
    while (open < in[i]) {
      res += '(';
      open++;
    }
    res += ')';
  }
  stack<int> st;
  open = 0;
  int close = 0;
  for (int i = 0; i < n + n; i++) {
    if (res[i] == '(') st.push(++open);
    else {
      if (st.top() != in[close++]) {
        cout << ":(" << endl;
        return 0;
      }
      st.pop();
    }
  }
  cout << res << endl;
  return 0;	
}