E. Сколько различных

Дана последовательность из $n$ чисел. Для каждого её префикса выведите, сколько в нём различных значений.

Первая строка содержит число $n$ ($1 \le n \le 10^5$).

Вторая строка содержит $n$ целых чисел, по модулю не превосходящих $10^9$.

Выведите $n$ чисел: количество различных среди первых $1, 2, \dots, n$ элементов.