Masala E

Nodir, Gavhar, Gulnoza, Yahyo va Umid birgalikda NGGYU™ kompaniyasiga asos solishdi. Kompaniyaning asosiy ustuvorlik vazifasi MEX haqida masala ishlash.

MEX - Minimum Excluded, massivda yo’q bo’lgan eng kichkina nomanfiy butun son. Masalan $\text{MEX}([1, 2, 0, 5]) = 3$va $\text{MEX}([1, 3]) = 0$.

Sizga $N$ta elementdan iborat $a[1], a[2], ..., a[N]$ massiv berilgan.

Berilgan $k$ son uchun, $a$ massivni bir-nechta bo’laklarga bo’lishingiz mumkin. Agar har bir bo’lakning $\text{MEX}$ qiymati $k$dan oshmasa, u holda bu ajratish yaxshi deyiladi. $f(k)$ deb, yaxshi ajratishdagi minimal bo’laklar soniga aytiladi.

Barcha $1 ≤ k ≤ N$ uchun $f(k)$ qiymatini toping.

Birinchi qatorda sizga $N$ soni beriladi.
Ikkinchi qatorda $a[1], a[2], ..., a[N]$.

Chegaralar
• $1 ≤ N ≤ 10^6$
• $0 ≤ a[i] < N$, barcha $1 ≤ i ≤ N$ uchun

Subtasks
1. (7 ball) $N ≤ 100$
2. (7 ball) $N ≤ 1000$
3. (7 ball) $N ≤ 3000$
4. (7 ball) $N ≤ 5000$.
5. (7 ball) $N ≤ 10 000$.
6. (7 ball) $N ≤ 20 000$.
7. (7 ball) $N ≤ 30 000$.
8. (7 ball) $N ≤ 40 000$.
9. (9 ball) $N ≤ 100 000$.
10. (7 ball) $N ≤ 150 000$.
11. (7 ball) $N ≤ 250 000$.
12. (7 ball) $N ≤ 350 000$.
13. (7 ball) $N ≤ 500 000$.
14. (7 ball) Qo’shimcha chegaralarsiz.

Yagona qatorda $N$ta butun son - $f(1), f(2), ..., f(N)$ chiqaring