Giao lưu

Points: 400
Time limit: 1.0s
Memory limit: 1G

Authors:
Problem type

English Statement ( below ): Socialise

Đợt tập huấn 3H có $$N$$ bạn học sinh tham gia. Bạn thứ $$i$$ được đánh giá khả năng là số nguyên dương $$a_i$$. Tại buổi học thứ $$x$$, mỗi bạn tự tính cho mình một chỉ số khả năng là $$\lfloor \frac{a_i}{x} \rfloor$$ và các bạn có cùng chỉ số khả năng sẽ ngồi với nhau tạo thành một nhóm trao đổi và giao lưu.

Yêu cầu: với mỗi giá trị $$g = 1, 2, \dots N$$, hãy xác định xem buổi học sớm nhất xuất hiện nhóm có $$g$$ học sinh. (Ghi ra $$-1$$ nếu không tồn tại)

Dữ liệu vào:

• Dòng đầu chứa số nguyên dương $$N$$
• Dòng tiếp theo chứa $$N$$ só nguyên không âm $$a_1, a_2, \dots, a_n$$

Dữ liệu ra:

• Xuất ra $$n$$ dòng, dòng thứ $$i$$ là buổi học sớm nhất để có $$g$$ học sinh. Hoặc in ra $$-1$$ nếu không tồn tại

Giới hạn:

• Subtaks 1: $$n \leq 100$$ and $$a_i \leq 2.10^5$$
• Subtaks 2: $$n \leq 300$$ and $$a_i \leq 3.10^6$$
• Subtaks 3: $$n \leq 300$$ and $$a_i \leq 5.10^7$$

Input 1:

3
1 2 5


Output 1:

1
3
6

Giải thích
Ngày 1: $$x[d] =$$ { $$\lfloor \frac{1}{1} \rfloor, \lfloor \frac{2}{1} \rfloor, \lfloor \frac{5}{1} \rfloor$$ } $$=$$ { $$1, 2, 5$$ } — Nhóm đầu tiên có giá trị 1: Một trong các nhóm {$$1$$} {$$2$$} {$$5$$}
Ngày 2: $$x[d] =$$ { $$\lfloor \frac{1}{2} \rfloor, \lfloor \frac{2}{2} \rfloor, \lfloor \frac{5}{2} \rfloor$$ } $$=$$ { $$0, 1, 2$$ }
Ngày 3: $$x[d] =$$ { $$\lfloor \frac{1}{3} \rfloor, \lfloor \frac{2}{3} \rfloor, \lfloor \frac{5}{3} \rfloor$$ } $$=$$ { $$0, 0, 1$$ } — Nhóm đầu tiên có giá trị 2: Chỉ có nhóm {$$1, 2$$}
Ngày 4: $$x[d] =$$ { $$\lfloor \frac{1}{4} \rfloor, \lfloor \frac{2}{4} \rfloor, \lfloor \frac{5}{4} \rfloor$$ } $$=$$ { $$0, 0, 1$$ }
Ngày 5: $$x[d] =$$ { $$\lfloor \frac{1}{5} \rfloor, \lfloor \frac{2}{5} \rfloor, \lfloor \frac{5}{5} \rfloor$$ } $$=$$ { $$0, 0, 1$$ }
Ngày 6: $$x[d] =$$ { $$\lfloor \frac{1}{6} \rfloor, \lfloor \frac{2}{6} \rfloor, \lfloor \frac{5}{6} \rfloor$$ } $$=$$ { $$0, 0, 0$$ } — Nhóm đầu tiên có giá trị 3: Chỉ có nhóm {$$1, 2, 5$$}

Input 2:

3
1 1 5


Output 2:

1
1
6

Giải thích
Ngày 1: $$x[d] =$$ { $$\lfloor \frac{1}{1} \rfloor, \lfloor \frac{1}{1} \rfloor, \lfloor \frac{5}{1} \rfloor$$ } $$=$$ { $$1, 1, 5$$ } — Nhóm đầu tiên có giá trị 1: Một trong các nhóm {$$1$$} {$$1$$} {$$5$$}
Ngày 2: $$x[d] =$$ { $$\lfloor \frac{1}{2} \rfloor, \lfloor \frac{1}{2} \rfloor, \lfloor \frac{5}{2} \rfloor$$ } $$=$$ { $$0, 0, 2$$ } — Nhóm đầu tiên có giá trị 2: Chỉ có nhóm {$$1, 1$$}
Ngày 3: $$x[d] =$$ { $$\lfloor \frac{1}{3} \rfloor, \lfloor \frac{1}{3} \rfloor, \lfloor \frac{5}{3} \rfloor$$ } $$=$$ { $$0, 0, 1$$ }
Ngày 4: $$x[d] =$$ { $$\lfloor \frac{1}{4} \rfloor, \lfloor \frac{1}{4} \rfloor, \lfloor \frac{5}{4} \rfloor$$ } $$=$$ { $$0, 0, 1$$ }
Ngày 5: $$x[d] =$$ { $$\lfloor \frac{1}{5} \rfloor, \lfloor \frac{1}{5} \rfloor, \lfloor \frac{5}{5} \rfloor$$ } $$=$$ { $$0, 0, 1$$ }
Ngày 6: $$x[d] =$$ { $$\lfloor \frac{1}{6} \rfloor, \lfloor \frac{1}{6} \rfloor, \lfloor \frac{5}{6} \rfloor$$ } $$=$$ { $$0, 0, 0$$ } — Nhóm đầu tiên có giá trị 3: Chỉ có nhóm {$$1, 2, 5$$}

Input 3:

3
2 2 2


Output 3:

-1
-1
2

Giải thích
Ngày 1: $$x[d] =$$ { $$\lfloor \frac{2}{1} \rfloor, \lfloor \frac{2}{1} \rfloor, \lfloor \frac{2}{1} \rfloor$$ } $$=$$ { $$2, 2, 2$$ } — Nhóm đầu tiên có giá trị 3: Chỉ có nhóm {$$2, 2, 2$$}
Ngày 2: $$x[d] =$$ { $$\lfloor \frac{2}{2} \rfloor, \lfloor \frac{2}{2} \rfloor, \lfloor \frac{2}{2} \rfloor$$ } $$=$$ { $$0, 0, 0$$ }
Ngày 3: $$x[d] =$$ { $$\lfloor \frac{2}{3} \rfloor, \lfloor \frac{2}{3} \rfloor, \lfloor \frac{2}{3} \rfloor$$ } $$=$$ { $$0, 0, 0$$ }
Ngày 3 $$\leq k \rightarrow \infty$$: $$x[d] =$$ { $$\lfloor \frac{2}{k} \rfloor, \lfloor \frac{2}{k} \rfloor, \lfloor \frac{2}{k} \rfloor$$ } $$=$$ { $$0, 0, 0$$ } — Không có nhóm có giá trị 1 hay 2

English Statement: Socialise

There are $$N$$ buildings with $$a_1, a_2, \dots, a_n$$ metters height. These days are hard, the heavy raining weather still not ended yet. In day $$d$$, every building with height $$h$$ only have $$x_d = \lfloor \frac{h}{d} \rfloor$$ height left of good space to use, while others are sunk underwater. Every building having the same value $$x_d$$ on day $$d$$ will group together (including $$x_d = 0$$ which sunk completely underwater) in a way that no other building with same value $$x_d$$ in another group.

Queries: In each size $$s$$ from $$1$$ to $$n$$, what is the earliest day $$d$$ that have at least one group of size $$s$$

Input:

• First line with positive integer $$N$$
• Second line with $$N$$ non-negative height $$a_1, a_2, \dots, a_n$$

Output:

• Output $$n$$ lines, the line $$s-th$$ should consist the earliest day that have a group of size $$s$$. If there is no such group exists then output $$-1$$.

Constraint:

• Subtaks 1: $$n \leq 100$$ and $$a_i \leq 2.10^5$$
• Subtaks 2: $$n \leq 300$$ and $$a_i \leq 3.10^6$$
• Subtaks 3: $$n \leq 300$$ and $$a_i \leq 5.10^7$$

Input 1:

3
1 2 5


Output 1:

1
3
6

Explanation
Day 1: $$x[d] =$$ { $$\lfloor \frac{1}{1} \rfloor, \lfloor \frac{2}{1} \rfloor, \lfloor \frac{5}{1} \rfloor$$ } $$=$$ { $$1, 2, 5$$ } — First group of size 1: Any of {$$1$$} {$$2$$} {$$5$$}
Day 2: $$x[d] =$$ { $$\lfloor \frac{1}{2} \rfloor, \lfloor \frac{2}{2} \rfloor, \lfloor \frac{5}{2} \rfloor$$ } $$=$$ { $$0, 1, 2$$ }
Day 3: $$x[d] =$$ { $$\lfloor \frac{1}{3} \rfloor, \lfloor \frac{2}{3} \rfloor, \lfloor \frac{5}{3} \rfloor$$ } $$=$$ { $$0, 0, 1$$ } — First group of size 2: Only {$$1, 2$$}
Day 4: $$x[d] =$$ { $$\lfloor \frac{1}{4} \rfloor, \lfloor \frac{2}{4} \rfloor, \lfloor \frac{5}{4} \rfloor$$ } $$=$$ { $$0, 0, 1$$ }
Day 5: $$x[d] =$$ { $$\lfloor \frac{1}{5} \rfloor, \lfloor \frac{2}{5} \rfloor, \lfloor \frac{5}{5} \rfloor$$ } $$=$$ { $$0, 0, 1$$ }
Day 6: $$x[d] =$$ { $$\lfloor \frac{1}{6} \rfloor, \lfloor \frac{2}{6} \rfloor, \lfloor \frac{5}{6} \rfloor$$ } $$=$$ { $$0, 0, 0$$ } — First group of size 3: Only {$$1, 2, 5$$}

Input 2:

3
1 1 5


Output 2:

1
1
6

Explanation
Day 1: $$x[d] =$$ { $$\lfloor \frac{1}{1} \rfloor, \lfloor \frac{1}{1} \rfloor, \lfloor \frac{5}{1} \rfloor$$ } $$=$$ { $$1, 1, 5$$ } — First group of size 1: Any of {$$1$$} {$$1$$} {$$5$$}
Day 2: $$x[d] =$$ { $$\lfloor \frac{1}{2} \rfloor, \lfloor \frac{1}{2} \rfloor, \lfloor \frac{5}{2} \rfloor$$ } $$=$$ { $$0, 0, 2$$ } — First group of size 2: Only {$$1, 1$$}
Day 3: $$x[d] =$$ { $$\lfloor \frac{1}{3} \rfloor, \lfloor \frac{1}{3} \rfloor, \lfloor \frac{5}{3} \rfloor$$ } $$=$$ { $$0, 0, 1$$ }
Day 4: $$x[d] =$$ { $$\lfloor \frac{1}{4} \rfloor, \lfloor \frac{1}{4} \rfloor, \lfloor \frac{5}{4} \rfloor$$ } $$=$$ { $$0, 0, 1$$ }
Day 5: $$x[d] =$$ { $$\lfloor \frac{1}{5} \rfloor, \lfloor \frac{1}{5} \rfloor, \lfloor \frac{5}{5} \rfloor$$ } $$=$$ { $$0, 0, 1$$ }
Day 6: $$x[d] =$$ { $$\lfloor \frac{1}{6} \rfloor, \lfloor \frac{1}{6} \rfloor, \lfloor \frac{5}{6} \rfloor$$ } $$=$$ { $$0, 0, 0$$ } — First group of size 3: Only {$$1, 2, 5$$}

Input 3:

3
2 2 2


Output 3:

-1
-1
2

Explanation
Day 1: $$x[d] =$$ { $$\lfloor \frac{2}{1} \rfloor, \lfloor \frac{2}{1} \rfloor, \lfloor \frac{2}{1} \rfloor$$ } $$=$$ { $$2, 2, 2$$ } — First group of size 3: Only {$$2, 2, 2$$}
Day 2: $$x[d] =$$ { $$\lfloor \frac{2}{2} \rfloor, \lfloor \frac{2}{2} \rfloor, \lfloor \frac{2}{2} \rfloor$$ } $$=$$ { $$0, 0, 0$$ }
Day 3: $$x[d] =$$ { $$\lfloor \frac{2}{3} \rfloor, \lfloor \frac{2}{3} \rfloor, \lfloor \frac{2}{3} \rfloor$$ } $$=$$ { $$0, 0, 0$$ }
Day 3 $$\leq k \rightarrow \infty$$: $$x[d] =$$ { $$\lfloor \frac{2}{k} \rfloor, \lfloor \frac{2}{k} \rfloor, \lfloor \frac{2}{k} \rfloor$$ } $$=$$ { $$0, 0, 0$$ } — There are no group of size 1 and 2