Problem Description

Mirko held $N$ parties, one each day. On the $i$-th party, he invites $i$ people to each table.

Mirko prepared $N$ tables, and there are $V_i$ candies on the $i$-th table.

After all invited people sit down, the people at the same table share the candies on that table equally. In other words, on day $i$, at table $j$, each person sitting at that table will get $\left\lfloor \dfrac{V_j}{i} \right\rfloor$ candies.

The number of candies is updated every day, and it does not decrease because of sharing.

Only tables where the candies per person are the same will socialize.

Now, for each positive integer $s$ from $1$ to $N$, Mirko wants you to find the earliest day on which exactly $s$ tables socialize.

Input Format

The first line contains a positive integer $N$, representing the number of parties.

The second line contains $N$ positive integers $V_i$, where $V_i$ is the number of candies on the $i$-th table.

Output Format

Output $N$ lines in total. Each line contains one integer. The $i$-th line should be the earliest day on which exactly $i$ tables socialize. If there is no day on which exactly $i$ tables socialize, output -1.

5
11 10 9 6 4 

1
2
3
6
12

3
5 5 5

-1
-1
1

8
12 16 95 96 138 56 205 84

1
5
14
49
96
97
139
206

Hint

Sample Explanation #1.

On the first day, no table will socialize with any other table.

On the second day, at tables $1$ and $2$, everyone gets $5$ candies, so these two tables will socialize.

On the third day, at tables $1$, $2$, and $3$, everyone gets $3$ candies, so these three tables will socialize.

On the sixth day, at tables $1$, $2$, $3$, and $4$, everyone gets $1$ candy, so these four tables will socialize.

On the twelfth day, at tables $1$, $2$, $3$, $4$, and $5$, everyone gets $0$ candies, so these five tables will socialize.

Constraints.

For $100\%$ of the testdata, $1 \le N \le 100$, $1 \le V_i \le 10^8$.

Source.

The score of this problem follows the original COCI problem setting, with a full score of $140$.

This problem is translated from COCI2013-2014 CONTEST #4 T5 ČOKOLADE.

Translated by ChatGPT 5