Codeforces Round #204 (Div. 2)->A. Jeff and Digits

Jeff's got n cards, each card contains either digit 0, or digit 5. Jeff can choose several cards and put them in a line so that he gets some number. What is the largest possible number divisible by 90 Jeff can make from the cards he's got?

Jeff must make the number without leading zero. At that, we assume that number 0 doesn't contain any leading zeroes. Jeff doesn't have to use all the cards.

Input

The first line contains integer n (1 ≤ n ≤ 103). The next line contains n integers a1, a2, ..., an (ai = 0 or ai = 5). Number ai represents the digit that is written on the i-th card.

Output

In a single line print the answer to the problem — the maximum number, divisible by 90. If you can't make any divisible by 90 number from the cards, print -1.

Examples

input

4
5 0 5 0

output

input

11
5 5 5 5 5 5 5 5 0 5 5

output

5555555550

Note

In the first test you can make only one number that is a multiple of 90 — 0.

In the second test you can make number 5555555550, it is a multiple of 90.

题意：给出n个数字，数字只有两种，0或者5，随意组合这些数字，问是否可以找到能组合出的数中能被90整除的最大的数。

题解：根据给出的样例，其实我们已经知道了前两个能被90整除的数，第一个是0，第二个是9个5加1个0，然后我们用计算器算一下，就可以知道，当5的个数是9的倍数并且有0存在时，这个数是可以整除90的，所以，只需要统计0和5的个数balabala(看代码....

#include<bits/stdc++.h>
using namespace std;
int n, k5 = 0, k0 = 0, tmp;
int main() {
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> tmp;
        if(tmp == 5)
            k5++;
        else
            k0++;
    }
    if(k0 == 0) {
        cout << -1 << endl;
        return 0;
    }
    if(k5 < 9 && k0) {
        cout << 0 << endl;
        return 0;
    }
    if(k5) {
        int aa = k5 / 9;
        int bb = aa * 9;
        while(bb--)
            cout << 5;
        while(k0--)
            cout << 0;
        cout << endl;
        return 0;
    }
    return 0;
}

Codeforces Round #204 (Div. 2)->A. Jeff and Digits

相关推荐