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;


int N, P[100000];

int main() {
  cin >> N;
  for(int i = 0; i < N; i++) {
    cin >> P[i];
    --P[i];
  }
  stack< int > st;

  string tap;
  for(int i = N - 1; i >= 0; i--) {
    while(st.size() && st.top() > P[i]) {
      tap += "(";
      st.pop();
    }
    tap += ")";
    st.push(P[i]);
  }
  while(st.size()) {
    tap += "(";
    st.pop();
  }
  reverse(tap.begin(), tap.end());


  int ptr1 = 0, ptr2 = 0;
  for(int i = 0; i < tap.size(); i++) {
    if(tap[i] == '(') {
      st.emplace(ptr1++);
    } else {
      if(st.empty() || P[ptr2++] != st.top()) {
        cout << ":(" << endl; // うくやめてえ
        return 0;
      }
      st.pop();
    }
  }

  cout << tap << endl;

}

C++: #include "bits/stdc++.h"
#include<vector>
#include<iostream>
#include<queue>
#include<algorithm>
#include<map>
#include<set>
#include<iomanip>
#include<assert.h>
#include<unordered_map>
#include<unordered_set>
#include<string>
#include<stack>
#include<complex>
#pragma warning(disable:4996)
using namespace std;
using ld = long double;
template<class T>
using Table = vector<vector<T>>;
const ld eps=1e-9;
	
#define WHATS(var)//cout<<__LINE__<<' '<<#var<<"="<<var<<endl;
	
template<class S, class T> ostream& operator <<(ostream &os, const pair<S, T> v){
	os << "( " << v.first << ", " << v.second << ")"; return os;
}
template<class T> ostream& operator <<(ostream &os, const vector<T> &v){
	for(int i = 0; i < v.size(); i++){if(i > 0){os << " ";} os << v[i];} return os;
}
template<class T> ostream& operator <<(ostream &os, const vector<vector<T>> &v){
	for(int i = 0; i < v.size(); i++){if(i > 0){os << endl;} os << v[i];} return os;
}
template<class T> ostream& operator <<(ostream &os, const vector<set<T>> &v){
	for(int i = 0; i < v.size(); i++){if(i > 0){os << endl;} os << v[i];} return os;
}
template<class T> ostream& operator <<(ostream &os, const set<T> &v){
	int i=0;
	for(auto it:v){
		if(i > 0){os << ' ';}
		os << it;
		i++;
	} 
	return os;
}


	
int main() {
	ios::sync_with_stdio(false);
	int N;cin>>N;
	string answer;
	int now=0;
	stack<int>sta;
	for(int i=0;i<N;++i){
		int x;cin>>x;x--;
		while(x>=now){
			sta.emplace(now);
			now++;
			answer+="(";
		}
		if(sta.top()==x){
			sta.pop();
			answer+=")";
			
		}else{
			break;
		}
	}
	
	if(answer.size()!=2*N)answer=":(";
	cout<<answer<<endl;
	return 0;	
}

C++: #include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "string"
#include "map"
#include "unordered_map"
#include "unordered_set"
#include "iomanip"
#include "cmath"
#include "random"
#include "bitset"
#include "cstdio"
#include "numeric"
#include "cassert"

using namespace std;

const long long int MOD = 1000000007;
//const int MOD = 998244353;

long long int N, M, K, H, W, L, R;
//int N, M, K, H, W, L, R


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

	cin >> N;
	vector<int>p(N + 1);
	vector<int>v(N + 1);
	for (int i = 1; i <= N; i++) {
		cin >> p[i];
		v[p[i]] = i;
	}
	vector<long long int>closed(N + 1);
	vector<long long int>place(N + 1);
	vector<long long int>op(N + 1);
	for (int i = 1; i <= N; i++)place[i] = closed[i] = i * MOD;
	int m = N;
	for (int i = N; i >= 1; i--) {
		op[i] = --place[min(v[i], m)];
		m = min(m, v[i]);
	}
	//for (int i = 1; i <= N; i++)cout << v[i] << endl;
	vector<pair<long long int, int>>ret;
	for (int i = 1; i <= N; i++) {
		ret.push_back({ op[i],1 });
		ret.push_back({ closed[i],-1 });
	}
	sort(ret.begin(), ret.end());
	vector<int>box(N + 1);
	stack<int>st;
	int usedop = 1;
	int usedcl = 1;
	for (int i = 0; i < ret.size(); i++) {
		if (ret[i].second == 1)st.push(usedop++);
		else {
			box[st.top()] = usedcl++;
			st.pop();
		}
	}
	if (v != box) {
		cout << ":(\n";
		return 0;
	}
	for (auto i : ret) {
		if (i.second == 1)cout << '(';
		else cout << ')';
	}
	cout << endl;
}