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>
using namespace std;

#define INF_LL (int64)1e18
#define INF (int32)1e9
#define REP(i, n) for(int64 i = 0;i < (n);i++)
#define FOR(i, a, b) for(int64 i = (a);i < (b);i++)
#define all(x) x.begin(),x.end()
#define fs first
#define sc second

using int32 = int_fast32_t;
using uint32 = uint_fast32_t;
using int64 = int_fast64_t;
using uint64 = uint_fast64_t;
using PII = pair<int32, int32>;
using PLL = pair<int64, int64>;

const double eps = 1e-10;

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;}

int main(void){
	cin.tie(0);
	ios::sync_with_stdio(false);

	int64 n;
	string s = "";
	cin >> n;
	vector<int64> a(n);
	REP(i, n) cin >> a[i];
	stack<int64> st;
	int64 maxi = 0;
	REP(i, n) {
		while (maxi < a[i]) {
			maxi++;
			st.push(maxi);
			s += "(";
		}
		if (st.top() != a[i]) {
			cout << ":(" << endl;
			return 0;
		}
		s += ")";
		st.pop();
	}
	cout << s << endl;
}

C++: #include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#define rep(i,s,e) for(int (i) = (s);(i) <= (e);(i)++)
#define all(x) x.begin(),x.end()

int n;
string ans = "";

int p[101010];

int q[101010];

int main() {
  cin >> n;
  for(int i = 0;i < n;i++) {
    cin >> p[i];
  }
  for(int i = 0;i < n;i++) {
    q[p[i]] = i + 1;
  }

  vector<int> vec;

  int cnt = 1;

  for(int i = 1;i <= n;i++) {
    vec.push_back(q[i]);
    ans += "(";
    while(!vec.empty() && vec.back() == cnt) {
      ans += ")";
      vec.pop_back();
      cnt++;
    }
  }
  if(ans.size() == 2 * n)
    cout << ans << endl;
  else {
    cout << ":(" << endl;
  }
}

C++: /*  -*- coding: utf-8 -*-
 *
 * 2931.cc: 
 */

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<functional>
 
using namespace std;

/* constant */

const int MAX_N = 100000;

/* typedef */

typedef stack<int> sti;

/* global variables */

int qs[MAX_N];
char s[MAX_N * 2 + 4];
sti st;

/* subroutines */

/* main */

int main() {
  int n;
  scanf("%d", &n);

  for (int i = 0; i < n; i++) {
    int pi;
    scanf("%d", &pi);
    pi--;
    qs[pi] = i;
  }
  //for (int i = 0; i < n; i++) printf("%d ", qs[i]); putchar('\n');

  for (int i = 0, j = 0, k = 0; i < n || j < n; i++) {
    while (! st.empty() && st.top() == j)
      s[k++] = ')', j++, st.pop();

    if (i >= n) {
      if (j < n) {
	puts(":(");
	return 0;
      }
      break;
    }

    st.push(qs[i]);
    s[k++] = '(';
  }

  puts(s);
  return 0;
}

C++: #include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
const int INF=1e9,MOD=1e9+7;
const ll LINF=1e18;
using namespace std;
#define int long long
//template
//main
signed main(){
  int N;cin>>N;
  std::vector<int> v(N);
  for(int i=0;i<N;i++)cin>>v[i];
  string ans;
  stack<int> sta;
  int a=1;
  for(int i=0;i<N;i++){
    while(v[i]>=a){sta.push(a++);ans+='(';}
    int k=sta.top();sta.pop();
    if(k!=v[i]){cout<<":("<<endl;return 0;}
    ans+=')';
  }
  cout<<ans<<endl;
}

C++: #include <bits/stdc++.h>
using namespace std;
//#define DEBUG_MODE
#define endl '\n'
#ifdef DEBUG_MODE
#define DEBUG(X) debug_func(X, #X)
#define DEBUG_ENDL endl
#define DEBUG_SEPARATOR_LINE cout<<"=================\n"
#else
#define DEBUG(X) 0
#define DEBUG_ENDL 0
#define DEBUG_SEPARATOR_LINE 0
#endif
#define ALL(V) (V).begin(), (V).end()
#define ALLR(V) (V).rbegin(), (V).rend()
#define DEBUG_ENDL_S(S) ((S).size() ? "\n" : "")
template <typename T> using V = vector<T>;
template <typename T> using VV = V<V<T>>;
template <typename T, typename U> using P = pair<T, U>;
using ll = int64_t;
using PLL = P<ll, ll>;
template <typename T> const T& var_min(const T &t) { return t; }
template <typename T> const T& var_max(const T &t) { return t; }
template <typename Head, typename... Tail> const Head& var_min(const Head &head, const Tail&... tail) { return min(head, var_min(tail...)); }
template <typename Head, typename... Tail> const Head& var_max(const Head &head, const Tail&... tail) { return max(head, var_max(tail...)); }
template <typename T, typename... Tail> void chmin(T &t, const Tail&... tail) { t = var_min(t, tail...); }
template <typename T, typename... Tail> void chmax(T &t, const Tail&... tail) { t = var_max(t, tail...); }
void debug_func_preffix(const string &s) { if(s.size()) cout << s << " = "; }
template <typename T>
void debug_func(const T &t, const string &s = "") {
    debug_func_preffix(s);
    cout << t << DEBUG_ENDL_S(s);
}
template <typename T, typename U>
void debug_func(const P<T, U> &p, const string &s = "") {
    debug_func_preffix(s);
    cout << "(";
    debug_func(p.first);
    cout << ", ";
    debug_func(p.second);
    cout << ")" << DEBUG_ENDL_S(s);
}
template <typename T>
void debug_func(const V<T> &v, const string &s = "") {
    for(ll i = 0; i < v.size(); i++) {
        string t = s + "[" + to_string(i) + "]";
        debug_func(v[i], t);
    }
}

const ll INF = 5e15;

int main() {
    ll N;
    cin >> N;
    V<ll> P(N);
    for(ll &e : P) {
        cin >> e;
        e--;
    }
    {
        auto tmp = P;
        for(ll i = 0; i < N; i++) P[tmp[i]] = i;
    }
    DEBUG(P);
    P.push_back(N);
    string ans;
    V<bool> watched(N + 10, false);
    ll want = 0;
    ll pre = INF;
    bool padded = false;
    for(ll i = 0; i < N; i++) {
        ans += '(';
        watched[P[i]] = true;
        bool added = false;
        for(; watched[want] && want < N; want++) {
            ans += ')';
            added = true;
        }
        if(!added) {
            DEBUG(pre);
            DEBUG(P[i]);
            if(pre < P[i] && !padded) {
                cout << ":(\n";
                return 0;
            }
        }
        pre = P[i];
        DEBUG(ans);
        padded = added;
    }
    cout << (ans.size() == 2 * N ? ans : ":(") << endl;
    return 0;
}

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;
 
}