蜗蜗得到了一些卡片,这些卡片上标有数字 $0$ 或 $5$。现在他可以选择其中一些卡片排成一行,使得排出的一行数字组成的数最大,且满足被 $90$ 整除这个条件(被 $90$ 整除意味着这个数是$90$的倍数)。同时,这个数必须为合法的某个非负整数,即不能含有前导 $0$,即 $0$ 不能作为这串数的首位。但是特殊地,整数 $0$ 满足条件。如果不能排出这样的数,输出 −1
。
输入格式
第一行,卡片的个数 $n$。
第二行,分别给出了这 $n$ 个数(只能为数字 $0$ 或 $5$)。
输出格式
仅一行,如果可以排出,则输出这个数,否则输出 -1
。
样例输入1
4
5 0 5 0
样例输出1
0
样例输入2
11
5 5 5 5 5 5 5 5 0 5 5
样例输出2
5555555550
样例输入3
2
5 5
样例输出3
-1
数据规模
对于 $30\%$ 的数据,$n\leq 10$。
对于另外 $20\%$ 的数据,仅含数字 $5$。
对于 $100\%$ 的数据,$n\leq 1000$。