How many times each number occurs

You are given an array of $n$ numbers. Find how many times each distinct number occurs. Print the numbers in the order of their first appearance in the array.

The first line contains $n$ ($1 \le n \le 10^5$). The second line contains $n$ integers ($|a_i| \le 10^9$).

A separate line for each distinct number: the number and its count.

A dictionary (dict / map) stores a value by key: the key is the number, the value is its counter. To keep the order, also write a number into a separate list when it appears for the first time (Python's dict keeps the order itself). In the first example: 1 3, 3 1, 2 2, 4 1, 9 1.

For $n = 10^5$ comparing every element with all others ($n^2 = 10^{10}$ operations) is too slow — a set or a dictionary does it in one pass.