407398: GYM102784 E Spooky Numbers

Francine loves pranks. Her friend, Buster, is not a Halloween fan and during the course of October, he has an unnatural fear of any non-negative number which is divisible by $$$2$$$, $$$3$$$, and $$$5$$$. At the sight or mention of any of these 'spooky' numbers, Buster jumps a little bit. Francine, always on the lookout for good prank opportunities, has noticed a pattern: the larger the 'spooky' number, the higher Buster seems to jump. Curious to see how high she can get him to jump, she wants comes up with a huge 'spooky' number and print the digits individually, and put the number across the school football field for Buster to see before practice. She finally gets to a 'spooky' number that she was happy with but then her friend Arthur got a hold of her laptop before she sent the order to be printed and added some random digits. Francine, unfortunately, did not realize Arthur's prank until after she sent the order to be printed and now she realizes that she is going to get more digits than she wanted.

In order to salvage the prank and not waste the digits she is getting, she asks you for help. She wants the largest 'spooky' number that can be made from the $$$n$$$ digits that she is having printed such that there are no leading zeros (leading zeros don't bother Buster so Francine doesn't want to go through all the effort of putting them up for no reason). Your job is to output the largest 'spooky' number that she can make with the $$$n$$$ digits she has (or output $$$-1$$$ if there was a catastrophic error in Francine's calculations such that she cannot make a 'spooky' number with her digits).

The first line of input will contain a single integer, $$$n$$$ (where $$$1 \leq n \leq 10^{5}$$$), representing the number of digits Francine has.

The second line of input will have $$$n$$$ space-separated integers, where the $$$i$$$th number will be $$$d_i$$$ (where $$$0 \leq d_i \leq 9$$$) representing the value of a single digit that Francine has.

The largest 'spooky' number that Francine can make with her digits (without any leading zeros) or $$$-1$$$ if it is not possible to make a 'spooky' number.

1
0

0

6
2 3 1 3 1 0

33210

In the first example, the only digit is $$$0$$$ so there is only one 'spooky' number which can be made, namely $$$0$$$. In the second example, the largest 'spooky' number that can be made is $$$33210$$$, no number which includes all $$$6$$$ of the digits can be divisible by $$$3$$$ so this is the best we can do.