“罪犯解放粗暴小队”（Criminal Liberating Rough Squad，简称 CLRS）计划袭击一列正穿过沙漠前往另一座监狱的囚犯押运列车，并解救其中的部分囚犯。

CLRS 拥有 10 辆卡车，用于将解救出的罪犯从袭击地点运送到临时机场，飞机已经在那里加好油，准备将罪犯送往国外。

在袭击现场，CLRS 会闯入一节火车车厢，制服车厢守卫，解救该车厢内的所有囚犯，然后移动到下一节车厢。小队将从第一节被袭击的车厢开始，向列车尾部推进，逐一解救各车厢内的罪犯。CLRS 自豪地宣称，他们将解救并装载任何他们袭击的车厢内的所有罪犯。CLRS 在列车上只朝一个方向移动，绝不回头。

奇怪的是，当卡车离开现场时，所有卡车上装载的获救罪犯人数必须完全相同。这是 CLRS 的一项古老安全迷信，在任何此类行动中都绝对不能打破。

但也有坏消息。警察很可能就在附近巡逻，因此在最初的袭击之后，必须尽快离开现场。也就是说，一旦满足上述迷信规则，就必须立即离开。

任务也可能无法完成。例如，如果 CLRS 在离列车尾部太近的车厢开始袭击，就可能无法完成任务。

现在，一切都必须仔细规划。CLRS 事先知道每节车厢中押运的罪犯人数。他们想知道，对于列车上的每一节车厢，如果从该车厢开始袭击，他们需要袭击多少节车厢。

输入格式

第一行包含一个整数 $N$ ($1 \le N \le 10^5$)，表示列车上的车厢数量。第二行包含 $N$ 个介于 0 到 9（含）之间的数值，表示每节车厢中押运的罪犯人数。这些数值按列车从第一节到最后一节的顺序排列。

输出格式

输出由 $N$ 个数字组成的序列，其中第 $k$ 个值表示从第 $k$ 节车厢开始袭击时所袭击的车厢总数。如果从第 $k$ 节车厢开始无法完成任务，则序列中对应的值为 $-1$。

样例

输入 1

5
0 2 4 6 8

输出 1

1 4 2 -1 -1

输入 2

5
5 5 5 0 5

输出 2

2 2 3 1 -1