Description

犯罪解放粗暴小队（CLRS）计划袭击一列正在穿越沙漠、押送囚犯去另一座监狱的火车，并解救其中至少一部分囚犯。

CLRS 恰好有 10 辆卡车，这些卡车将把被解救的罪犯从袭击地点运送到临时机场，飞机已经在加油，准备将罪犯带出国。

在袭击现场，CLRS 会闯入一节车厢，制服车厢守卫，释放该车厢内的所有囚犯，然后前往下一节车厢。小队会从最先被袭击的车厢开始，依次向火车末端推进，逐节释放囚犯。CLRS 自豪地宣称，他们会释放并装载所有被袭击车厢内的罪犯到卡车上。CLRS 在火车上只会朝一个方向前进，绝不会回头。

有些奇怪的是，离开现场时，每辆卡车上被解救的罪犯人数必须完全相同。这是 CLRS 长久以来的安全迷信，无论如何都不能违反。

还有坏消息。警方很可能会在附近巡逻，因此袭击后必须尽快离开现场。也就是说，只要满足迷信规则，就要立即撤离。

也有可能任务无法完成。例如，如果 CLRS 从距离火车末端太近的车厢开始袭击。

现在，一切都必须精心策划。CLRS 事先知道每节车厢内被押送的罪犯人数。他们想知道，对于火车上的每一节车厢，如果从该车厢开始袭击，需要袭击多少节车厢。

Input Format

第一行包含一个整数 $N$（$1 \leq N \leq 10^5$），表示火车上的车厢数量。第二行包含 $N$ 个介于 0 到 9 之间的整数，分别表示每节车厢内被押送的罪犯人数，顺序从火车头到火车尾。

Output Format

输出包含 $N$ 个数字，第 $k$ 个数字表示如果从第 $k$ 节车厢开始袭击，需要袭击多少节车厢。如果从第 $k$ 节车厢开始无法完成任务，则对应位置输出 $-1$。

5
0 2 4 6 8

1 4 2 -1 -1

5
5 5 5 0 5

2 2 3 1 -1

Hint

由 ChatGPT 4.1 翻译