#include <bits/stdc++.h>
using namespace std;
namespace maxmin {
template <class T>
T max(T&& a) {
  return a;
}
template <class T>
T min(T&& a) {
  return a;
}
template <class T>
T max(T&& a, T&& b) {
  return a > b ? a : b;
}
template <class T>
T min(T&& a, T&& b) {
  return a < b ? a : b;
}
template <class T, class... Ts>
T max(T&& a, Ts&&... ts) {
  T b = max(ts...);
  return a > b ? a : b;
}
template <class T, class... Ts>
T min(T&& a, Ts&&... ts) {
  T b = min(ts...);
  return a < b ? a : b;
}
template <class T, class... Ts>
T chmax(T&& a, Ts&&... ts) {
  a = max(a, ts...);
  return a;
}
template <class T, class... Ts>
T chmin(T&& a, Ts&&... ts) {
  a = min(a, ts...);
  return a;
}
}  // namespace maxmin
namespace input {
template <class T>
void re(T&& x) {
  cin >> x;
}
template <class T1, class T2>
void re(pair<T1, T2>& p) {
  re(p.first);
  re(p.second);
}
template <class T>
void re(vector<T>& a) {
  for (int i = 0; i < (int)(a).size(); i++) re(a[i]);
}
template <class T1, class T2>
void rea(T1&& a, T2 t) {
  for (int i = 0; i < t; i++) re(a[i]);
}
template <class T1, class T2>
void rea1(T1&& a, T2 t) {
  for (int i = 1; i <= t; i++) re(a[i]);
}
template <class T, class... Ts>
void re(T&& t, Ts&... ts) {
  re(t);
  re(ts...);
}
}  // namespace input
namespace output {
void pr(int x) { cout << x; }
void pr(bool x) { cout << x; }
void pr(long long x) { cout << x; }
void pr(long long unsigned x) { cout << x; }
void pr(double x) { cout << x; }
void pr(char x) { cout << x; }
void pr(const string& x) { cout << x; }
void pr(const char* x) { cout << x; }
void pr(const char* x, size_t len) { cout << string(x, len); }
void ps() { pr("\n"); }
void pw() { pr(" "); }
void pc() { pr("]\n"); }
bool parse(const char* t) {
  if (t == "\n") return true;
  return false;
}
template <class T>
void pr(const T&);
template <class T>
bool parse(T&& t) {
  return false;
}
template <class T1, class T2>
void psa(T1&& a, T2 t) {
  for (int i = 0; i < t; i++) pr(a[i]), pr(" ");
  ps();
}
template <class T1, class T2>
void psa2(T1&& a, T2 t1, T2 t2) {
  for (int i = 0; i < t1; i++) {
    for (int j = 0; j < t2; j++) pr(a[i][j]), pr(" ");
    ps();
  }
}
template <class T1, class T2>
void pr(const pair<T1, T2>& x) {
  pr("{");
  pr(x.first);
  pr(", ");
  pr(x.second);
  pr("}");
}
template <class T>
void pr(const T& x) {
  pr("{");
  bool fst = 1;
  for (const auto& a : x) pr(!fst ? ", " : ""), pr(a), fst = 0;
  pr("}");
}
template <class T, class... Ts>
void pr(const T& t, const Ts&... ts) {
  pr(t);
  pr(ts...);
}
template <class T, class... Ts>
void ps(const T& t, const Ts&... ts) {
  pr(t);
  if (sizeof...(ts)) {
    if (!parse(t)) pr(" ");
  }
  ps(ts...);
}
template <class T>
void pwv(const T& x) {
  for (const auto& a : x) pr(a), pw();
  ps();
}
template <class T, class... Ts>
void pw(const T& t, const Ts&... ts) {
  pr(t);
  if (sizeof...(ts)) pr(" ");
  pw(ts...);
}
template <class T, class... Ts>
void pc(const T& t, const Ts&... ts) {
  pr(t);
  if (sizeof...(ts)) pr(", ");
  pc(ts...);
}
namespace trace {
template <class T1, class T2>
void __f(const char* name, const T1& x, const T2& y) {
  pr("[", y, "] = ");
  ps(x);
}
template <class T1, class T2, class... Ts>
void __f(const char* name, const T1& x, const T2& y, const Ts&... rest) {
  const char* open = strchr(name, '[');
  pr("[", y, "]");
  __f(open + 1, x, rest...);
}
template <class T1, class T2, class... Ts>
void __f0(const char* name, const T1& x, const T2& y, const Ts&... rest) {
  const char* open = strchr(name, '[');
  pr(name, size_t(open - name));
  __f(name, x, y, rest...);
}
template <class T>
void __fn(int n, const char* name, const T& x) {
  for (int i = 0; i < n; i++) pr(name), __f(name, x[i], i);
}
}  // namespace trace
}  // namespace output
using namespace maxmin;
using namespace input;
using namespace output;
using namespace output::trace;
using pii = pair<int, int>;
using ll = long long;
const int N = 2e5 + 5;
int frq[10];
int32_t main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  ;
  int i, n, a, sum = 0;
  re(n);
  for (i = 0; i < n; i++) re(a), frq[a]++, sum += a;
  if (!frq[0]) return ps(-1), 0;
  if (sum % 3) {
    for (i = sum % 3; i <= 9; i += 3) {
      if (frq[i]) {
        frq[i]--;
        break;
      }
    }
    if (i > 9) {
      int bad = 2;
      for (i = sum % 3 == 1 ? 2 : 1; i <= 9; i += 3) {
        if (frq[i]) {
          int x = min(bad, frq[i]);
          frq[i] -= x;
          bad -= x;
        }
        if (!bad) break;
      }
      if (i > 9) return ps(-1), 0;
    }
  }
  string ans;
  for (i = 9; i; i--)
    while (frq[i]) ans += (char)('0' + i), frq[i]--;
  while (frq[0]) ans += (char)('0' + 0), frq[0]--;
  if (ans.front() == '0')
    ps(0);
  else
    ps(ans);
  return 0;
}

### Prompt

Construct a cpp code solution to the problem outlined:

Furik loves math lessons very much, so he doesn't attend them, unlike Rubik. But now Furik wants to get a good mark for math. For that Ms. Ivanova, his math teacher, gave him a new task. Furik solved the task immediately. Can you?

You are given a set of digits, your task is to find the maximum integer that you can make from these digits. The made number must be divisible by 2, 3, 5 without a residue. It is permitted to use not all digits from the set, it is forbidden to use leading zeroes.

Each digit is allowed to occur in the number the same number of times it occurs in the set.

Input

A single line contains a single integer n (1 ≤ n ≤ 100000) — the number of digits in the set. The second line contains n digits, the digits are separated by a single space. 

Output

On a single line print the answer to the problem. If such number does not exist, then you should print -1.

Examples

Input

1
0


Output

0


Input

11
3 4 5 4 5 3 5 3 4 4 0


Output

5554443330


Input

8
3 2 5 1 5 2 2 3


Output

-1

Note

In the first sample there is only one number you can make — 0. In the second sample the sought number is 5554443330. In the third sample it is impossible to make the required number.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
namespace maxmin {
template <class T>
T max(T&& a) {
  return a;
}
template <class T>
T min(T&& a) {
  return a;
}
template <class T>
T max(T&& a, T&& b) {
  return a > b ? a : b;
}
template <class T>
T min(T&& a, T&& b) {
  return a < b ? a : b;
}
template <class T, class... Ts>
T max(T&& a, Ts&&... ts) {
  T b = max(ts...);
  return a > b ? a : b;
}
template <class T, class... Ts>
T min(T&& a, Ts&&... ts) {
  T b = min(ts...);
  return a < b ? a : b;
}
template <class T, class... Ts>
T chmax(T&& a, Ts&&... ts) {
  a = max(a, ts...);
  return a;
}
template <class T, class... Ts>
T chmin(T&& a, Ts&&... ts) {
  a = min(a, ts...);
  return a;
}
}  // namespace maxmin
namespace input {
template <class T>
void re(T&& x) {
  cin >> x;
}
template <class T1, class T2>
void re(pair<T1, T2>& p) {
  re(p.first);
  re(p.second);
}
template <class T>
void re(vector<T>& a) {
  for (int i = 0; i < (int)(a).size(); i++) re(a[i]);
}
template <class T1, class T2>
void rea(T1&& a, T2 t) {
  for (int i = 0; i < t; i++) re(a[i]);
}
template <class T1, class T2>
void rea1(T1&& a, T2 t) {
  for (int i = 1; i <= t; i++) re(a[i]);
}
template <class T, class... Ts>
void re(T&& t, Ts&... ts) {
  re(t);
  re(ts...);
}
}  // namespace input
namespace output {
void pr(int x) { cout << x; }
void pr(bool x) { cout << x; }
void pr(long long x) { cout << x; }
void pr(long long unsigned x) { cout << x; }
void pr(double x) { cout << x; }
void pr(char x) { cout << x; }
void pr(const string& x) { cout << x; }
void pr(const char* x) { cout << x; }
void pr(const char* x, size_t len) { cout << string(x, len); }
void ps() { pr("\n"); }
void pw() { pr(" "); }
void pc() { pr("]\n"); }
bool parse(const char* t) {
  if (t == "\n") return true;
  return false;
}
template <class T>
void pr(const T&);
template <class T>
bool parse(T&& t) {
  return false;
}
template <class T1, class T2>
void psa(T1&& a, T2 t) {
  for (int i = 0; i < t; i++) pr(a[i]), pr(" ");
  ps();
}
template <class T1, class T2>
void psa2(T1&& a, T2 t1, T2 t2) {
  for (int i = 0; i < t1; i++) {
    for (int j = 0; j < t2; j++) pr(a[i][j]), pr(" ");
    ps();
  }
}
template <class T1, class T2>
void pr(const pair<T1, T2>& x) {
  pr("{");
  pr(x.first);
  pr(", ");
  pr(x.second);
  pr("}");
}
template <class T>
void pr(const T& x) {
  pr("{");
  bool fst = 1;
  for (const auto& a : x) pr(!fst ? ", " : ""), pr(a), fst = 0;
  pr("}");
}
template <class T, class... Ts>
void pr(const T& t, const Ts&... ts) {
  pr(t);
  pr(ts...);
}
template <class T, class... Ts>
void ps(const T& t, const Ts&... ts) {
  pr(t);
  if (sizeof...(ts)) {
    if (!parse(t)) pr(" ");
  }
  ps(ts...);
}
template <class T>
void pwv(const T& x) {
  for (const auto& a : x) pr(a), pw();
  ps();
}
template <class T, class... Ts>
void pw(const T& t, const Ts&... ts) {
  pr(t);
  if (sizeof...(ts)) pr(" ");
  pw(ts...);
}
template <class T, class... Ts>
void pc(const T& t, const Ts&... ts) {
  pr(t);
  if (sizeof...(ts)) pr(", ");
  pc(ts...);
}
namespace trace {
template <class T1, class T2>
void __f(const char* name, const T1& x, const T2& y) {
  pr("[", y, "] = ");
  ps(x);
}
template <class T1, class T2, class... Ts>
void __f(const char* name, const T1& x, const T2& y, const Ts&... rest) {
  const char* open = strchr(name, '[');
  pr("[", y, "]");
  __f(open + 1, x, rest...);
}
template <class T1, class T2, class... Ts>
void __f0(const char* name, const T1& x, const T2& y, const Ts&... rest) {
  const char* open = strchr(name, '[');
  pr(name, size_t(open - name));
  __f(name, x, y, rest...);
}
template <class T>
void __fn(int n, const char* name, const T& x) {
  for (int i = 0; i < n; i++) pr(name), __f(name, x[i], i);
}
}  // namespace trace
}  // namespace output
using namespace maxmin;
using namespace input;
using namespace output;
using namespace output::trace;
using pii = pair<int, int>;
using ll = long long;
const int N = 2e5 + 5;
int frq[10];
int32_t main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  ;
  int i, n, a, sum = 0;
  re(n);
  for (i = 0; i < n; i++) re(a), frq[a]++, sum += a;
  if (!frq[0]) return ps(-1), 0;
  if (sum % 3) {
    for (i = sum % 3; i <= 9; i += 3) {
      if (frq[i]) {
        frq[i]--;
        break;
      }
    }
    if (i > 9) {
      int bad = 2;
      for (i = sum % 3 == 1 ? 2 : 1; i <= 9; i += 3) {
        if (frq[i]) {
          int x = min(bad, frq[i]);
          frq[i] -= x;
          bad -= x;
        }
        if (!bad) break;
      }
      if (i > 9) return ps(-1), 0;
    }
  }
  string ans;
  for (i = 9; i; i--)
    while (frq[i]) ans += (char)('0' + i), frq[i]--;
  while (frq[0]) ans += (char)('0' + 0), frq[0]--;
  if (ans.front() == '0')
    ps(0);
  else
    ps(ans);
  return 0;
}

```