Domnul Map vă pune la dispoziție un șir a[1], a[2], …, a[n] de numere naturale.

Cerința

Pentru fiecare a[i] (i=1..n) trebuie să spuneți de câte ori apare acest element în secvența a[1], a[2], …, a[i].

Date de intrare

Fișierul de intrare map.in conține pe prima linie numărul n. Pe linia a doua, separate prin câte un spațiu, sunt elementele șirului.

Date de ieșire

În fișierul de ieșire map.out se vor afișa pe primul rând n numere naturale, al i-lea număr reprezentând numărul de apariții ale lui a[i] în secvența a[1], a[2], …, a[i].

Restricții și precizări

• 1 ≤ n ≤ 200 000
• 0 <= a[i] <= 1018

Exemplu:

map.in

7
1 9876543210 1 3 3 9876543210 9876543210

map.out

1 1 2 1 2 2 3

Explicație

Primul element este 1. Apare o singură dată până acum.
Al doilea element este 9876543210. Și el apare pentru prima dată.
Al treilea element este 1. Apare a doua oară.
Al patrulea element este 3. Apare prima oară.
Al cincilea element este 3. Apare a doua oară.
Al șaselea element este 9876543210. Apare a doua oară.
Al șaptelea element este 9876543210. Apare a treia oară.