题目描述

Jeff 有 $n$ 张卡片，每张卡片上写有数字 $0$ 或 $5$。Jeff 可以选择若干张卡片，将它们排成一行，组成一个数。请问 Jeff 能用这些卡片组成的、能够被 $90$ 整除的最大数是多少？

生成的数不能有前导零。这里我们认为数字 $0$ 没有前导零。Jeff 可以不使用所有卡片。

输入格式

第一行包含一个整数 $n$ $(1 \leq n \leq 10^{3})$，表示卡片的数量。
第二行包含 $n$ 个整数 $a_{1}, a_{2}, \ldots, a_{n}$，其中 $a_{i}=0$ 或 $a_{i}=5$。数字 $a_i$ 表示第 $i$ 张卡片上写的数字。

输出格式

一行输出问题的答案，即能够被 $90$ 整除的最大数。如果无法组成任何一个能被 $90$ 整除的数，则输出 $-1$。

说明/提示

在第一个测试样例中，只能组成一个能被 $90$ 整除的数，即 $0$。

在第二个测试样例中，可以组成数 $5555555550$，它是 $90$ 的倍数。

由 ChatGPT 5 翻译

样例

4
5 0 5 0

0

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

5555555550