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 ≤ 10^3). The next line contains n integers a_1, a_2, ..., a_{n} (a_{i} = 0 or a_{i} = 5). Number a_{i} 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
0

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.

Difficulty: interview

Starter code:

Solutions:
from math import*
from random import*

# input = open(file = "input.txt", mode = "r")
# output = open(file = "output.txt", mode = "w")
# list(map(int, input().split()))

n = int(input())
A = list(map(int, input().split()))
z, f = 0, 0
for i in range(n):
    if A[i] == 0:
        z += 1
    else:
        f += 1
if (z == 0):
    print(-1)
    return
if (f // 9 == 0):
    print(0)
else:
    print ("5" * (f - f % 9) + "0" * z)

input()
A = input().split()
count5 = 0
for elem in A:
    if elem == '5':
        count5 += 1
count0 = len(A) - count5
if count0 == 0:
    print(-1)
else:
    print(int('5' * ((count5 // 9) * 9) + '0' * count0))


#!/usr/bin/env python
n = int(input())
nums = [int(x) for x in input().split()]

fives = 0
zeros = 0

for n in nums:
    if n == 5: 
        fives += 1
    elif n == 0:
        zeros += 1

if (zeros < 1):
    print(-1)
else:
    actfives = (fives // 9) * 9
    if (actfives > 0):
        print('5' * actfives + '0' * zeros)
    else:
        print(0)



N = int(input())
Numbers = list(map(int, input().split()))
Zeros, Fives = 0, 0
for Num in Numbers:
    if Num == 0:
        Zeros += 1
    else:
        Fives += 1
if Zeros == 0:
    print(-1)
elif Fives < 9:
    print(0)
else:
    print("5" * (Fives // 9 * 9) + "0" * Zeros)


n=int(input())

A=list(map(int,input().split()))

A.sort()

if(A.count(0)==0):
    print(-1)
else:
    ans="0"*A.count(0)
    x=A.count(5)
    while((x*5)%9!=0):
        x-=1
    ans=("5"*x)+ans
    if( "5" not in ans ):
        print(0)
    else:
        print(ans)


n = int(input())
a = sorted(list(map(int, input().split())))[::-1]
i = 0
if (a[-1] == 5):
    print(-1)
else:
    while (a[i] == 5):
        i += 1
    if (i < 9):
        if (i < n):
            print(0)
        else:
            print(-1)
    else:
        for j in range(i - i % 9):
            print('5', end = '')
        for j in range(n - i):
            print('0', end = '')

n = int(input())
d = dict()
d[5] = 0
d[0] = 0
a = list(map(int, input().split()))
for i in range(n):
	d[a[i]] += 1
d[5] -= d[5] % 9
if d[5] == 0 and d[0] == 0:
	print(-1)
elif d[5] == 0:
	print(0)
elif d[0] == 0:
	print(-1)
else:
	for i in range(d[5]):
		print(5, sep = '', end = '')
	for i in range(d[0]):
		print(0, sep = '', end = '')


n = int(input())
s = list(map(int, input().split()))
k = 0
m = 0
for i in range(len(s)):
    if s[i] == 0:
        k += 1
    else:
        m += 1
if k == 0:
    print(-1)
elif m < 9:
    print(0)
else:
    x = m // 9
    print('5' * 9 * x + '0' * k)


n, cards = int(input()), sorted(input().split())
print(int(max(('555555555' * (cards.count('5') // 9) + '0' * cards.count('0')) * (cards.count('0') != 0), '-1')))


def __starting_point():
    inp = input()
    arr = input().split(' ')
    cz =0
    cf =0
    for a in arr:
        if int(a)==0:
            cz+=1
        if int(a)==5:
            cf+=1
    ans = '-1'
##    print(cf)
##    print(cz)
    if cz==0:
        ans = '-1'
    else:
        ng = cf//9
        ans = '555555555'*ng+'0'*cz
    print(int(ans))
        
        

__starting_point()

n = int(input())
a = list(map(int,input().split()))
c5 = 0
c0 = 0
for j in a:
    if j == 5:
        c5+=1
    else:
        c0+=1
if c5<9:
    if c0>0:
        print(0)
        return
    else:
        print(-1)
        return
else:
    if c0>0:
        print(int("5"*(c5-c5%9)+'0'*c0))
    else:
        print(-1)


n = int(input())
arr = list(map(int, input().split()))
c0 = arr.count(0)
c5 = n - c0
if c5 >= 9 and c0 > 0:
    str = ((c5//9) * 9) * '5'
    str += c0 * '0'
elif c0 >= 1:
    str = '0'
else:
    str = '-1'
print(str)


n = int(input())
cards  = list(map(int, input().split()))
five = cards.count(5) - (cards.count(5) % 9)
zero = cards.count(0)
if zero == 0:
	print(-1)
elif five == 0:
	print(0)
else:
	print('5'*five+zero*'0')
	


while(1):
    try:
        n=int(input())
        a=list(map(int,input().split()))
        count5=a.count(5)
        count0=a.count(0)
        if count5//9==0 and count0!=0:
            print(0)
        elif  count0==0:
            print(-1)
        else:
            print((count5//9)*9*'5'+count0*'0')
    except EOFError:
        break
        


n=int(input())
m=list(map(int,input().split()))
if 0 in m :
    if 5 in m:
        k=0
        l=0
        for i in range(n):
            k+=m[i]
            if m[i]==0:
                l+=1
        p=k//9
        #print(p)
        p1=p//5
        #print(p1)
        if p1 !=0:
            print('5'*p1*9+'0'*l)
        else:
            print(0)
    else:
        print(0)
else :
    print(-1)

n = int(input())
seq = list(map(int, input().split()))

five = 0
zero = 0

for i in seq:
    if i == 5:
        five += 1
    elif i == 0:
        zero += 1

if five >= 9:
    mod = five % 9
    if zero >= 1:
        print((five - mod) * '5' + zero * '0')
    else:
        print(-1)
else:
    if zero > 0:
        print(0)
    else:
        print(-1)

n = int(input())
a = list(map(int, input().split()))

count0 = 0
count5 = 0
for i in range(n):
  if a[i] == 5:
    count5 += 1
  else:
    count0 += 1

if count0 == 0:
  print(-1)
elif count5 < 9:
  print(0)
else:
  print('5' * (count5 - count5 % 9) + '0' * count0)

n = int(input())
arr = list(map(int, input().split()))
fives = 0 
if 5 in arr:
    fives = arr.count(5)
nulls = n - fives
fives -= fives % 9
if nulls == 0 :
    print(-1)
else:
    print(int(str(5) * fives + str(0) * nulls))

num = int(input())
cards = input().split(' ')

for i in range(num):
    cards[i] = int(cards[i])

num_5 = 0
num_0 = 0
result = ''
for i in range(num):
    if cards[i] == 5:
        num_5 += 1
    if cards[i] == 0:
        num_0 += 1

if num_0 == 0:
    print(-1)
elif num_5 // 9 < 0:
    print(-1)
else:
    result = '5' * ((num_5 // 9) * 9) + '0' * num_0
    print(int(result))


n = int(input())
s5 = 0
s0 = 0
ar = list(input().split())
for i in range(n):
    if ar[i] == '5':
        s5 += 1
    else:
        s0 += 1
while s5 % 9 and s5:
    s5 -= 1
if s5 and s0:
    print(s5*'5' + '0'*s0)
elif s0:
    print(0)
else:
    print(-1)

# your code goes here

import string

n = int ( input() )

str = input()
L = str.split()
S = 0
Szero = 0
Sfive = 0

while n>0:
    S+=int(L[n-1])
    if int(L[n-1]) == 0:
        Szero+=1
    else:
        Sfive+=1
    n-=1
    
newstr = ""
    
if Sfive>=9 and Szero>0:

    i = int ( Sfive/9 )
    i = i*9
    while i>0:
        newstr += '5'
        i-=1
    
    i = Szero
    
    while i>0:
        newstr += '0'
        
        i-=1
    
    print (newstr)
elif Sfive<9 and Szero>0:
    print ("0")
else:
    print ("-1")


x=int(input())
y=[int(p) for p in input().split()]


x=a=y.count(5)
b=y.count(0)
while((x*5)%9!=0):
        x-=1
if(y.count(0)==0):
        print(-1)

elif(a!=0 and x!=0):
        print('5'*x+'0'*b)
elif(x==0):
        print(0)


import os
import sys
import math

fin = sys.stdin
if os.path.exists("in.txt"):
	fin = open("in.txt")


n = int(fin.readline().split()[0])
x = [int(i) for i in fin.readline().split()]
c0 = len([i for i in x if i == 0])
c5 = len([i for i in x if i == 5])
c5 = int(c5 / 9) * 9
if c0 == 0:
	print(-1)
elif c5 == 0:
	print(0)
else:
	s = ""
	for i in range(c5):
		s += "5"
	for i in range(c0):
		s += "0"
	print(s)

n, t = int(input()), input()
a = t.count('5')
b = n - a
print(int('5' * (a - a % 9) + '0' * b) if b else -1)

def main():
    n = int(input())
    nulls = fives = 0

    for item in input().split():
        if int(item)==0:
            nulls+=1
        else:
            fives+=1

    if nulls>=1:
        if fives>=9:
            print(int('5'*(fives-fives%9)+'0'*nulls))
        else:
            print(0)
    else:
        print(-1)

main()