题目描述

小T 要解救一辆火车中的部分囚犯。 小T 拥有 10 辆卡车，用于将解救的囚犯从袭击现场运往临时机场。

小T 的袭击方式如下：

• 从某一节车厢开始闯入，释放该车厢所有囚犯，然后继续向火车尾部方向依次袭击后续车厢。
• 每袭击一节车厢，就释放该车厢所有囚犯，并立即将他们装载到卡车上。
• 他们只能朝火车尾部方向前进，不会回头。

小T 有一个奇怪的安全迷信：

• 离开现场时，每辆卡车上的囚犯人数必须完全相同。

此外，警方可能在附近巡逻，因此一旦满足迷信条件，就必须立即撤离，不会继续袭击更多车厢。

任务可能失败的情况：

• 如果从某一节车厢开始袭击，直到最后一节车厢都无法让每辆卡车人数相同，则任务失败。

简单来说，已知火车有 $N$ 节车厢，每节车厢的囚犯人数（0 到 9 之间）按从车头到车尾的顺序给出。 对于每一节车厢 $k$，假设 小T 从它开始袭击，你需要帮忙计算：

• 最少袭击多少节车厢（包括开始车厢）才能让总解救人数是 10 的倍数（因为 10 辆卡车，每辆人数相同）。
• 如果直到最后一节车厢都无法满足条件，则输出 -1。

输入格式

第一行：整数 $N$（$1 \le N \le 10^5$），车厢数量。 第二行：$N$ 个整数 $a_1, a_2, \dots, a_N$（$0 \le a_i \le 9$），表示每节车厢的囚犯人数。

输出格式

输出 $N$ 个整数，用空格隔开。 第 $k$ 个数表示从第 $k$ 节车厢开始袭击时，需要袭击的最少车厢数（若不可能则输出 -1）。

输入输出样例

输入样例 1

5
0 2 4 6 8

输出样例 1

1 4 2 -1 -1

数据范围

对于40%的数据满足：

• $1 \leq N \leq 10^3$

对于100%的数据满足：

• $1 \leq N \leq 10^5$