Description

HXY has some cards, each labeled with the digit $0$ or $5$.

She can choose some of these cards and arrange them in a row to form the largest possible number that is divisible by $90$.

This number must be a valid non-negative integer, meaning it cannot have a leading $0$; that is, $0$ cannot be the first digit of the sequence.

Exceptionally, the integer $0$ is allowed.

If no such number can be formed, output $-1$.

Input Format

The first line contains the number of cards $n$.

The second line contains the $n$ digits (each is either $5$ or $0$).

Output Format

Output a single line: if it is possible, print the number; otherwise, print $-1$.

4
5 0 5 0

0

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

5555555550

2
5 5

-1

Hint

Constraints:

For $30\%$ of the testdata, $n \le 10$.

For $20\%$ of the testdata, all given digits are $5$.

For $100\%$ of the testdata, $n \le 1000$.

Translated by ChatGPT 5