Сколько раз каждое число

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

В первой строке $n$ ($1 \le n \le 10^5$). Во второй — $n$ целых чисел ($|a_i| \le 10^9$).

Для каждого различного числа отдельная строка: число и количество его вхождений.

Словарь (dict / map) хранит значение по ключу: ключ — число, значение — счётчик. Чтобы сохранить порядок, при первом появлении числа записывайте его ещё и в отдельный список (dict в Python хранит порядок сам). В первом примере: 1 3, 3 1, 2 2, 4 1, 9 1.

При $n = 10^5$ сравнение каждого элемента со всеми остальными ($n^2 = 10^{10}$ операций) не уложится во время — множество или словарь справляются за один проход.