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ă.

#include <bits/stdc++.h>

using namespace std;

ifstream cin("map.in");
ofstream cout("map.out");
map <long long , int> r;
long long n , s;

int main()
{
    cin >> n;
    for(int i = 1 ; i <= n ; i++)
    {
        cin >> s;
        r[s]++;
        cout << r[s] << " ";
    }
}