Система обрабатывает n последовательных обращений пользователей. Для каждого обращения известен идентификатор пользователя.

Для каждого обращения нужно определить, какой по счёту раз этот пользователь обращается к системе к текущему моменту, включая текущее обращение.

Иными словами, для каждого i требуется вывести, сколько раз идентификатор a_i встретился среди обращений с первого по i-е включительно.

Входные данные

Первая строка содержит одно целое число n — количество обращений.

Вторая строка содержит n целых чисел a_i — идентификаторы пользователей в порядке поступления обращений.

Выходные данные

Выведите n целых чисел через пробел — для каждого обращения номер этого появления данного пользователя среди всех обращений от начала до текущей позиции.

Ограничения

• 1 <= n <= 2 * 10^5
• -10^9 <= a_i <= 10^9

Примеры

Пример 1

Входные данные

1
7

Выходные данные

1

Пример 2

Входные данные

5
7 7 7 7 7

Выходные данные

1 2 3 4 5